boj.kr/2667 단지번호붙이기 (silver1) 파이썬 풀이

1. 모든 좌표를 순회하면서 아래를 반복

1.1. 값이 '1'인 경우 방문체크하고 집의 개수 d를 1으로 초기화한 후에 아래 dfs를 수행

1.1.1. 상하좌우 좌표값 중 값이 '1'이고 방문하지 않았으면 방문체크하고 dfs를 호출, 전역변수 d값을 1증감

1.1.2. dfs함수 밖에서 초기화했던 d를 반환

1.2. d_list에 dfs수행 결과 전역변수 d를 append

1.3. 영역의 개수 cnt를 1 증감

2. 영역의 개수 cnt를 출력하고 d_list를 오름차순으로 출력 

 

N = int(input())
board = [input().strip() for _ in range(N)]
visited = [[0]*N for _ in range(N)]

import sys
sys.setrecursionlimit(10**9)
dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
def dfs(y, x):
    global d
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny<N and 0<=nx<N and board[ny][nx] == '1' and visited[ny][nx] == 0:
            visited[ny][nx] += 1
            dfs(ny, nx)
            d += 1
    return d

cnt = 0
d_list = []
for y in range(N):
    for x in range(N):
        if board[y][x] == '1' and visited[y][x] == 0:
            visited[y][x] += 1
            d = 1
            d_list.append(dfs(y, x))
            cnt += 1
print(cnt)
for d in sorted(d_list):
    print(d)

 

bfs가 최단거리 찾기 문제에서 주로 사용할 수 있다면 dfs는 영역개수 찾기 문제에서 주로 사용할 수 있다.