https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 💡IDEA 트리, DFS를 사용하는 문제이다. 처음엔 큐를 사용하여 삭제한 노드에 연결된 모든 노드들을 -1로 갱신하여 지워주는 방법으로 풀었으나 99%에서 실패가 떴다. 찾아보니 0번 노드만 남은 경우에도 결과값이 1이여야 하는데, 0으로 출력되고 있었다. 이것을 해결하기 위해 여러 방법으로 수정했으나 도무지 알 수가 없어서 DFS를 사용했다. 삭제한 노드에 연결된 모든 노드들의 부모 노드..
https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 💡IDEA DFS, 백트래킹을 사용하는 문제이다. 숫자를 직접 하나씩 부등호에 따라 넣어주는 식의 브루트 포스가 가능하다. 백트래킹으로 0~9 숫자를 포함하고 포함하지 않고를 결정하며 부등호를 만족하는 수를 찾으면 된다. 레벨(깊이)가 0이거나 방문하지 않았고 두 수(들어가는 숫자 중 마지막 수, 현재 인덱스 값)를 부등호로 비교했을 때 정상적인 경우에 백트래킹을 수행한다. 현재 인덱스 값을 포함한 값으로 재..
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 💡IDEA DFS 또는 동적 계획법을 사용하는 문제이다. 1463. 1로 만들기 문제와 거의 동일한데, N을 1로 만드는 방법에 포함된 수를 출력해야 한다는 점이 달랐다. 1463번에서 사용했던 그대로 DFS를 수행하지만 왔던 길을 기억하는 path를 저장했다. N에서 세가지 방법으로 1을 만들었을 때 연산 횟수의 최솟값을 갱신하는 과정에서 path도 갱신해주면 된다. 문제 분류에 동적 계획법도 있어서 한 번 도전해보았는데, 메모리도 시간도 꽤나 많이 잡아먹어서 DFS로 푸는 쪽이 좋을 것 같다. 그래..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 💡IDEA DFS와 백트래킹을 사용하는 문제이다. 문제 자체는 쉽게 접근이 가능하지만 시간초과가 자꾸 발생해서 꽤 고생을 했다. 처음에는 방문 배열에 알파벳 자체를 넣었다 뺐다 하는 식으로 했지만 바로 시간초과가 발생했다. 알파벳을 쉽게 인식할 수 있는 방법을 생각해보다가 알파벳을 숫자로 바꾸어주는 ord 함수를 사용해서 알파벳 개수인 26개만큼의 길이의 배열을 만들어서 사용하기로 했다. ..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 💡IDEA DFS를 사용하는 문제이다. 행, 열, 파이프 방향 세 변수를 사용하여 DFS를 수행한다. 파이프 방향은 0이 가로, 1이 세로, 2가 대각선이다. 다음 파이프가 가로로 갈 수 있는 경우는 현재 파이프가 가로 혹은 대각선 인 경우이다. 가로로 가기 위해서는 다음 열 값이 범위 내에 있고, 빈 칸(0)이어야 한다. 다음 파이프가 세로로 갈 수 있는 경우는 현재 파..
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 💡IDEA 재귀와 DFS를 사용하는 문제이다. 조건을 만족하는 수열을 출력하기 위해서 요소의 방문을 확인할 배열 하나, 중복된 수열을 출력하는 것을 방지할 상수 하나가 필요하다. 중복 수열 제거용 상수는 깊이가 다를 때마다 초기화 해주어야 한다. 방문 확인 및 이전에 쓰인 요소 값과 같은지 확인해주며 DFS를 수행한다. 📌CODE import sys input = sys.stdin.readlin..
