[BOJ] 2667 - 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

import sys
n = int(input())
graph = [list(map(int, sys.stdin.readline().rstrip())) for i in range(n)]
visited = [[False] * n for i in range(n)]
num = 1
result = []
cnt = 0

def dfs(x,y):
    global cnt
    if 0 <= x < n and 0 <= y < n:
        if graph[x][y] != 0 and not visited[x][y]:
             visited[x][y] = True
             cnt += 1
             dfs(x + 1, y)
             dfs(x, y + 1)
             dfs(x - 1, y)
             dfs(x, y - 1)
             return True
        return False
    return False
        

for i in range(n):
    for j in range(n):
        cnt = 0
        if dfs(i, j) == True:
            result.append(cnt)
            

print(len(result))
result.sort()
for i in result:
    print(i)

지도의 모든 부분을 방문하며 확인해야 하므로 DFS, BFS 두 가지 방법 모두 풀 수 있는 전형적인 문제이다. 나는 재귀함수로 DFS를 구현하여 푸는 방법을 선택했다.

 

if graph[x][y] != 0 and not visited[x][y]:
             visited[x][y] = True
             cnt += 1
             dfs(x + 1, y)
             dfs(x, y + 1)
             dfs(x - 1, y)
             dfs(x, y - 1)
             return True
        return False

해당 노드가 0이 아니고 처음 방문하는 것이라면 전역 변수인 cnt를 증가시키고 동서남북 4방향의 노드에 대해서 다시 dfs 함수를 재귀적으로 실행하고 True를 리턴한다. 

 

for i in range(n):
    for j in range(n):
        cnt = 0
        if dfs(i, j) == True:
            result.append(cnt)

하나의 dfs 함수가 True를 리턴했다는 것은 그 노드로부터 갈 수 있는 모든 노드를 방문하고 돌아온 것이기 때문에 cnt는 방문한 노드의 개수만큼 증가되어있을 것이고 그것이 각 단지내 집의 수가 된다. cnt를 result 리스트에 추가하고 다시 0으로 초기화시켜 다른 단지의 집의 수를 구할 수 있도록 하였다.

 

느낀 점

이 문제는 이취코테에서 풀었던 '음료수 얼려먹기'([이취코테] 음료수 얼려 먹기) 문제와 비슷한 문제이다.

그때는 끝까지 못 풀었지만 비슷한 문제를 다시 만나니 풀 수 있어서 뿌듯했다.