9. 도미노(하)
View as PDF
도미노는 블록 하나를 넘어뜨리면 그 블록이 넘어지면서 다음 블록들을 넘어뜨리는 일이 연쇄적으로 반복되는 게임이다.
도미노간의 연결 관계가 주어지고 1번 도미노를 넘어뜨렸을 때, 몇 개의 도미노가 쓰러질지 알아내 보자.
하나의 블록에는 여러 개의 연결된 블록이 있을 수 있다.
입력
- 첫 줄에는 도미노의 개수 \(N\), 연결 관계의 수 \(M\)이 주어진다.\((2 ≤ N ≤ 2000, 1 ≤ M ≤ 2000)\)
- 다음 \(M\)개의 줄에는 \(a\) \(b\)가 주어진다. 이는 \(a\)블록을 넘어뜨렸을 때 \(b\)블록도 함께 넘어짐을 뜻한다. 블록의 번호는 \(1\)부터 \(N\)까지 매겨져 있다.
출력
- 1번 도미노를 넘어뜨렸을 때 1번 도미노를 포함해 총 몇 개의 도미노가 넘어지는지 출력한다.
입력 예시 1
4 4
1 2
2 3
3 1
4 1
출력 예시 1
3
힌트
- 이를 그래프로 표현한 뒤 1번 노드에서부터 탐색해 보자. BFS나 DFS 중 어떤 방법을 사용해도 무방하다.
- 트리에서의 탐색과는 다르게, 그래프에서의 탐색은 이미 방문한 노드를 다시 방문하는 경우가 생긴다. 이를 막으려면 어떻게 해야 하는가?
Comments
도미노이기 때문에 노드의 연결이 쌍방향이 아닌 단방향인걸 생각을 못해 헤맸습니다.
Good point!!
전형적인 트리 탐색의 문제입니다. 그럼 우리는 하나 더 생각해야 합니다. 왜 이 문제가 트리 탐색에 적합할까? 이를 이해하면, 우리가 배운 트리 탐색 알고리즘 2개, BFS와 DFS, 이 중 어떤 것이 이 문제에 적합할까 찾을 수 있을 것이라 생각합니다.