목록2026/01/27 (1)

민혁이의 IT스토리

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

www.acmicpc.net/problem/2667 문제 풀이 위에 그림 처럼 지도가 주어지고 연결된 영역을 찾아야 하므로 그래프 탐색 문제로 판단했다. 모든 정점을 방문해야해서 DFS 혹은 BFS 모드 가능하지만 비교적으로 쉬운 재귀를 이용한 DFS로 구현해 보았다. 추상화된 흐름문제의 요구 조건은 단지의 갯수와 하나의 단지에 몇개의 집이 있는지 물어본다. 단순하게 생각해보자, 일단 그래프를 정해진 방향으로 순회를 하면서 집(1)을 만나면 연결되어 있는 또 다른 집을 찾고, 업다면 다른 단지를 찾아서 또 다시 순회하면 된다. 이렇게 했을 때 시간복잡도는 O(N^2)이다. 1. 순회오른쪽으로 가면서 집을 찾는다. 2. 확인한 집은 지우고 단지 정복하기 3. 새로운 단지 찾기 해결 과정전체 지도를 순..
알고리즘/코딩테스트 2026. 1. 27. 15:14
이전 Prev 1 Next 다음