1260 - DFS와 BFS

문제 요약

1. Input으로 그래프 정보가 들어온다.
2. 그래프를 DFS로 탐색했을 때와 BFS로 탐색했을 때, 결과를 출력하라

접근법

먼저 Input으로 들어온 정보를 바탕으로 그래프를 그려준다.
E.g) | N1| N2|
|—|—|
| 1 | 2 |
| 1 | 3 |
| 1 | 4 |
| 2 | 4 |

위와 같이 들어온 그래프 정보를 바탕으로 아래와 같이 그래프를 그려준다.

그래프를 저장하는 방법은 크게 2가지를 선택할 수 있는데 인접행렬법과 링크드 리스트를 이용하는 방법이 있다. 필자는 문제를 해결하기 위해 인접행렬법을 사용하였다.

그래프를 저장하고 난뒤, 저장한 그래프를 DFS 탐색과 BFS 탐색을 수행해야 한다. DFS와 BFS의 차이를 잘 나타내주는 움짤이 있어 가지고 와 봤다.

위 그림을 보면 DFS는 시작 노드에서부터 첫번째 자식 노드, 첫번째 자식 노드의 첫번째 자식 노드, 첫번째 자식 노드의 첫번째 자식 노드의 첫번째 자식 노드 … 순으로 그래프를 탐색하고 BFS는 시작 노드에서부터 시작 노드의 모든 자식 노드, 모든 자식 노드의 모든 자식 노드, 모든 자식 노드의 모든 자식 노드의 모든 자식 노드 … 순으로 그래프를 탐색한다. 이런 DFS, BFS 탐색을 구현하기 위해서 Stack과 Queue를 사용한다. 아마 이 글을 읽고 있는 독자들은 모두 Stack, Queue를 알고 있다고 생각한다. 그러나 필자가 너무 글을 못쓰는 관계로 DFS, BFS에 대해 조금 더 알아보고 싶은 독자는 이 블로그를 읽어보면 도움이 될 것이라고 생각한다.

이 문제는 DFS, BFS를 사용하는 가장 기초적인 문제이기 때문에, 위 내용을 알고 있다면 정말 쉽게 구현할 수 있다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)