[백준 2667]-단지번호붙이기 Python

www.acmicpc.net/problem/2667

 

문제 풀이 

• 위에 그림 처럼 지도가 주어지고 연결된 영역을 찾아야 하므로 그래프 탐색 문제로 판단했다. 
• 모든 정점을 방문해야해서 DFS 혹은 BFS 모드 가능하지만 비교적으로 쉬운 재귀를 이용한 DFS로 구현해 보았다.

 

추상화된 흐름

문제의 요구 조건은  단지의 갯수와 하나의 단지에 몇개의 집이 있는지 물어본다. 

단순하게 생각해보자, 일단 그래프를 정해진 방향으로 순회를 하면서 집(1)을 만나면 연결되어 있는 또 다른 집을 찾고, 

업다면 다른 단지를 찾아서 또 다시 순회하면 된다. 이렇게 했을 때 시간복잡도는 O(N^2)이다. 

 

1. 순회

오른쪽으로 가면서 집을 찾는다.

 

2. 확인한 집은 지우고 단지 정복하기 

3. 새로운 단지 찾기

 

 해결 과정

1. 전체 지도를 순회하며 집(1)을 찾는다
2. 집을 발견하면 DFS를 시작하고, 방문한 집은 '0'으로 바꿔 재방문을 방지한다.
3. DFS가 한 번 끝날 때마다 반환된 카운트(단지 내 집의 수)를 리스트에 담는다.
4. 마지막에 리스트를 정렬하여 출력한다.

어려웠던 점

오랜만에 알고리즘 문제를 접하다 보니, 문제의 핵심인 점화식을 도출하는 과정에서 생각보다 많은 시간을 소요했다.

특히, 논리적으로 점화식을 잘 세웠다고 생각했음에도 불구하고, 실제 실행 시 종료 조건이 완벽하지 않아 무한 루프에 빠지거나 잘못된 값을 반환하는 시행착오를 겪었다.

 

 

 

전체 코드