[백준] 그래프 탐색 - DFS (골드 4~5) 코멘트 모음

🙋🏻 DFS를 사용하는 이유

DFS는 미로 탐색과 같이 목표 노드가 멀리 떨어져 있다는 가정이 존재할 때, BFS보다 유리하다.

 

1. 메모리 사용량이 BFS보다 적다.

한 경로의 탐색이 완전히 끝날 때까지 다른 경로상의 노드가 비교적 추가되지 않기 때문에

같은 거리상의 모든 노드를 큐에 저장해두는 BFS보다 메모리 사용량이 비교적 적다.

 

2. 경로 탐색에 유리하다.

BFS의 경우 같은 거리에 위치한 모든 경로를 점진적으로 탐색하지만,

DFS의 경우 각 경로를 끝까지 탐색하다가 목표를 찾을 경우 즉시 종료하기 때문에

멀리 떨어진 목표까지의 경로 탐색에 유리하다.

 

⭕️ 1240번 : 노드사이의 거리 (골드5)

• 문제 유형 : tree, graph, dfs, bfs
• 시간 복잡도 : O(n)
• 풀이 방식 :

- 트리 형태를 띄고 있기 때문에 두 노드 사이의 거리는 항상 일정하므로 dfs, bfs 탐색 둘 다 가능
- 현재 인덱스와 간선 가중치를 저장할 수 있는 Node 클래스를 이용
- 인접 리스트를 이용하여 간선 정보를 저장하고(트리의 루트 노드가 정해져 있기 않기 때문에 양방향으로 저장) dfs 탐색을 진행
- dfs 탐색은 방문 체크와 인접 리스트를 통해 연결된 노드 사이의 간선 가중치를 중첩해가며 원하는 노드가 나올 때까지 탐색
- 인접리스트를 이용한 dfs 탐색이기 때문에 시간복잡도는 O(V+E)지만 (V = n, E = n-1)이기 때문에 O(n)이 됨

 

⭕️ 1937번 : 욕심쟁이 판다 (골드3)

• 문제 유형 : dp, graph, dfs
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 해당 위치에서 이동할 수 있는 칸 수를 의미하는 2차원 dp배열, 재귀를 활용한 dfs 탐색 사용
- 모든 노드를 탐색하여 방문하지 않은 노드는 dfs 탐색
- dp[i][j]에서 4방향 탐색하여 이미 방문한 노드의 경우 이동 가능 칸 수를 알고 있는 것이기 때문에 1을 더한 값이 dp[i][j]의 값보다 크면 값을 바꾸고, 방문하지 않은 노드의 경우 dfs 탐색(재귀 이용)을 한 후 1을 더한 값이 dp[i][j]의 값보다 크면 값을 바꿈
- 4방향 탐색 후 정해진 dp[i][j]값이 이동 가능 최대 칸 수를 의미하는 max보다 크면 값을 변경

 

⭕️ 1103번 : 게임 (골드2)

• 문제 유형 : dp, graph, dfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 일반적인 bfs, dfs 탐색으로 최대 동전 이동 횟수를 구할려고 하면 이미 탐색한 위치를 중복 탐색하기 때문에 각 위치마다 4방향 탐색을 하게 되어 시간 복잡도가 O(4^(nm))이 됨
- 따라서 재귀를 이용한 dfs와 2차원 dp배열을 이용해서 최대 동전 이동 횟수를 구함
- 4방향 탐색에서 방문하지 않은 위치라면 dfs 탐색을 하고, 이미 탐색한 위치라면 미리 구한 동전 이동 횟수를 가져와 4방향 중 가장 큰 값에 +1 한 값을 dp배열에 저장
- 현재 위치에서 동전을 이동했는데 해당 위치가 구멍 혹은 보드 밖 위치라 게임이 종료되면 해당 방향으로는 무조건 1번만 이동시킬 수 있기 때문에 1을 가져와 나머지 방향의 값과 비교

 

⭕️ 3109번 : 빵집 (골드2)

• 문제 유형 : greedy, graph, dfs
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 맨 왼쪽 열의 한 노드부터 맨 오른쪽 열의 한 노드까지 서로 겹치지 않고 이어지는 경로의 최대 개수를 구하는 문제이기 때문에 dfs 사용
- 어느 한 노드에서 바로 오른쪽 열의 노드로 갈 수 있는 경우의 수는 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 3가지
- 맨 위쪽 행부터 시작하여(stack에 넣는 순서도 반대로하면 반대여도 무관) 경로를 찾을 경우 최대한 위쪽에 치우친 경로를 만들어야 이후 경로에 영향을 끼칠 확률이 줄어들기 때문에 오른쪽 대각선 아래, 오른쪽, 오른쪽 대각선 위 순으로 stack에 add(stack은 후입선출 방식이기 때문)
- stack에 push할때 visit을 true로 체크 할 경우 이후 다른 경로를 택 해야할 경우 사용하지 않는 노드 또한 방문한 것이 되기 때문에 stakc에서 pop한 후 다음 경로가 존재하는 경우에만 visit을 true로 체크
- stack에서 pop한 노드의 위치가 맨 오른쪽 열일 경우 조건에 만족하는 경로가 이어진 것이기 때문에 경로 개수를 증가