[그래프 탐색] 백준 2667번. 단지번호붙이기 (파이썬) | DFS, BFS

문제

백준 2667번

2667번: 단지번호붙이기

🎯 <그림 1>과 같은 형태가 주어졌을 때 <그림 2>와 같이 연결된 영역의 개수를 구하는 문제이다 

 

코드

import sys
input = sys.stdin.readline


def DFS(arr, i, j, num):
    # 방문 처리
    arr[i][j] = 0 
    house[num-1] += 1
    
    # 상하좌우 모두 방문
    if i+1 < N and arr[i+1][j] == 1: # ↓ 방문
        DFS(arr, i+1, j, num)
    if j+1 < N and arr[i][j+1] == 1: # → 방문
        DFS(arr, i, j+1, num)
    if i-1 >= 0 and arr[i-1][j] == 1: # ↑ 방문
        DFS(arr, i-1, j, num)
    if j-1 >= 0 and arr[i][j-1] == 1: # ← 방문
        DFS(arr, i, j-1, num)
    
    # 더 이상 방문할 곳이 없으면 순회 끝
    
    
N = int(input())
arr = []
for i in range(N):
    arr.append(list(map(int, list(input().strip()))))

num = 0 
house = []
for i in range(N):
    for j in range(N):
        # 연결된 영역을 조사한다
        if arr[i][j] == 1: 
            num += 1 # 단지 개수 추가
            house.append(0) # 집 개수 세기 시작
            DFS(arr, i, j, num) # 인접한 노드 방문
            
print(num)
house.sort()
for i in house:
    print(i)

 

 

설명

해결 포인트:

• 2차원 배열을 방문 여부를 담고 있는 배열로 생각한다.
• 방문 안 된 노드를 발견하면, 해당 노드를 시작점으로 해서 그래프 탐색(DFS 또는 BFS)을 한다.
• 탐색할 때 방문했으면 배열 값을 0으로 바꿔 방문 처리를 해주고 상하좌우로 인접한 노드를 모두 방문한다