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

🗂️ 문제

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

 

💡 접근법

DFS를 사용하여 연결된 집의 개수를 구한다.

 

이때 dx와 dy 리스트를 통해 현재 위치에서 상하좌우로 이동할 수 있게 하고, 이동한 좌표가 1) 지도 밖을 벗어나지 않는지, 2) 집이 존재하는지, 3) 방문한 적이 없는지를 확인한다.

 

모든 조건을 만족할 경우 재귀로 DFS를 수행하고, 수행한 횟수를 cnt로 계산한다.

해당 값이 단지에 속하는 집의 개수가 된다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())

house_num = []
visited = [[False] * N for _ in range(N)]

maps = []
for _ in range(N):
    maps.append(list(map(int, sys.stdin.readline().rstrip())))

# 상하좌우
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def DFS(x, y):
    global cnt
    visited[x][y] = True
    cnt += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:  # 지도 밖을 벗어나지 않는지 확인
            if maps[nx][ny] and not visited[nx][ny]:  # 집이 있고 방문한 적이 없는 경우
                DFS(nx, ny)

for x in range(N):
    for y in range(N):
        if maps[x][y] and not visited[x][y]:
            cnt = 0
            DFS(x, y)
            if cnt != 0:
                house_num.append(cnt)

print(len(house_num))
for h in sorted(house_num):
    print(h)

 

✅ 정답 확인