[백준] 2667 - 단지번호붙이기 [Python(파이썬)]

문제

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

2667번: 단지번호붙이기

 

풀이

이전 문제인 바이러스가 1차원 리스트 형태(정확히는 인접 리스트)의 그래프 탐색이었다면, 이 문제는 2차원 리스트 형태의 그래프 탐색이라고 할 수 있다. 이런 문제 유형의 경우 탐색할 방향을 좌표의 형태로 리스트에 담아놓은 후 for문을 통해 4방향 탐색을 진행하면 된다. 그 다음엔 조건문을 통해 다음에 방문할 노드가 범위를 초과하는지 체크한 후, 방문 여부를 결정하면 된다.

 

나는 재귀 구조를 이용해 탐색이 종료되면 집의 수(cnt)가 리턴되게끔 코드를 작성했다. 이 부분이 까다로운 경우 전역 변수를 하나 선언해주는 것도 괜찮을 것 같다. 마지막에 오름차순으로 정렬해주는 것도 잊지말자.

 

코드

import sys
import collections
sys.setrecursionlimit(10**6)

def dfs(y, x, cnt):
    visited[y][x] = 1
    cnt += 1
    for i in range(4): # 4방향 탐색
        ny = y+dy[i]
        nx = x+dx[i]
        if 0 <= ny < n and 0 <= nx < n: # 그래프의 범위를 초과하는지 체크
            if g[ny][nx] and not visited[ny][nx]:
                cnt = dfs(ny, nx, cnt)
    return cnt

n = int(sys.stdin.readline().strip())
g = [[int(x) for x in sys.stdin.readline().strip()] for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
# 탐색할 방향을 좌표의 형태로 저장
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
results = []
complex = 0

for i in range(n):
    for j in range(n):
        if g[i][j] and not visited[i][j]:
            results.append(dfs(i, j, 0))
            complex += 1

print(complex)
for result in sorted(results):
    print(result)