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

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

문제

 

백준 2667번 단지번호붙이기 문제입니다.

그래프를 탐색하는 문제이므로 BFS / DFS를 이용해서 풀 수 있습니다.

---

DFS

이 문제는 DFS / BFS 어느 것을 선택해도 풀 수 있습니다.

 

출력은 단지의 수와 단지 내 집의 수를 출력해야 하므로 Dictionary 내부에 저장하겠습니다.

result = dict()

# 예상 구조
# 1번 단지 : 10
# 2번 단지 : 5
# ...

 

그래프를 $(0,0)$ 부터 $(n-1, n-1)$까지 순회하며 집$(1)$에 해당하는 값을 찾습니다.

// 그래프 순회
for i in range(n) :
    for j in range(n) :

 

집을 찾았다면 그 자리에서 DFS / BFS 탐색을 수행합니다.

이때 대각선은 고려하지 않기 때문에 4방향으로만 탐색합니다.

 

더 이상 탐색할 곳이 없을 경우 → 스택이 비어있을 때

단지번호와 집의 수를 저장합니다.

 

그래프의 순회가 끝나면 결과 값을 출력합니다

 

전체코드는 다음과 같습니다.

import sys
# from collections import deque

input = sys.stdin.readline

n = int(input())
visited = [[ False for _ in range(n) ] for _ in range(n) ]
table = []
result = dict()
danji_count = 0

moves = [ [0,1], [0,-1], [1,0], [-1,0] ]

for _ in range(n) :
    table.append([ int(c) for c in input().strip()])

for i in range(n) :
    for j in range(n) :
        target = table[i][j]
                
        # 집을 찾았다면 DFS 탐색
        if target == 1 and not visited[i][j]:
            stack = []
            stack.append([i,j])
            visited[i][j] = True
            
            # 단지 내 집의 숫자
            house_count = 1
            
            while stack :
                temp = stack.pop()
                
                # 4방향 탐색
                for move in moves :
                    next_y = move[0] + temp[0]
                    next_x = move[1] + temp[1]
                    
                    # 다음 탐색 경로가 지도 내부에 있고 방문한 적이 없다면
                    if 0 <= next_x < n and 0 <= next_y < n and not visited[next_y][next_x] :
                        # 다음 탐색 경로가 집이라면 스택에 추가하며 Count 1 증가
                        if table[next_y][next_x] == 1 :
                            stack.append([next_y, next_x])
                            house_count += 1
                        
                        # 탐색한 곳은 다시 갈 이유가 없으므로 방문 처리
                        visited[next_y][next_x] = True
                        
            # 단지 번호와 집의 갯수를 저장
            result[danji_count] = house_count
            danji_count += 1
            
print(len(result))
for r in sorted(list(result.values())) :
    print(r)

 

BFS로 탐색할 경우 stack을 deque()로 변경하고 popleft()로 순회하는 것 외에는 같습니다.

 

시간 복잡도의 경우 그래프 탐색만 고려했을 때 $O(N^2)$ 이고 N의 최대 값은 25입니다.

한 지점에서 4방향 탐색을 수행하므로 최대 탐색 횟수는 $4 * 625 = 2500$입니다.

 

DFS는 36ms, BFS는 56ms가 나오네요.