백준 2667번: 단지 번호 붙이기(dfs)

import sys

input = sys.stdin.readline
tc = int(input())  # 지도의 크기 (N x N)
dx = [-1, 1, 0, 0]  # 상하좌우 이동
dy = [0, 0, -1, 1]  # 상하좌우 이동

# DFS 함수: 특정 좌표를 시작으로 연결된 집들의 크기를 구한다
def dfs(graph, visited, width, height):
    visited[height][width] = 1  # 현재 좌표 방문 처리
    count = 1  # 현재 집 포함 (단지 크기 초기값)
    for i in range(4):  # 상하좌우로 이동
        rx = width + dx[i]
        ry = height + dy[i]
        # 유효 범위 내에서, 방문하지 않았고, 집(1)이 있는 경우
        if 0 <= rx < len(graph[0]) and 0 <= ry < len(graph) and visited[ry][rx] == 0 and graph[ry][rx] == 1:
            count += dfs(graph, visited, rx, ry)  # 연결된 집 탐색하며 크기 증가
    return count

# 지도와 방문 여부 초기화
graph = []
visited = []

# 지도 입력 처리
for i in range(tc):
    graph.append(list(map(int, input().strip())))
    visited.append([0 for j in range(tc)])  # 방문 여부 초기화

c = 0  # 단지 수
lst = []  # 각 단지 크기를 저장할 리스트

# 지도 전체를 순회하며 단지를 찾음
for i in range(tc):
    for j in range(tc):
        if graph[i][j] == 1 and visited[i][j] == 0:  # 방문하지 않은 집 발견
            lst.append(dfs(graph, visited, j, i))  # 단지 크기를 계산해 저장
            c += 1  # 단지 수 증가

# 결과 출력
print(c)  # 총 단지 수 출력
lst.sort()  # 단지 크기 오름차순 정렬
for i in lst:
    print(i)  # 각 단지 크기 출력

문제 정의

• 지도는 0(빈 공간)과 1(집)으로 이루어진 N x N 크기의 정사각형 배열입니다.
• 연결된 집들은 하나의 "단지"로 정의됩니다. (대각선은 연결로 보지 않음)
• 출력해야 할 값:
  1. 단지의 개수
  2. 각 단지에 포함된 집의 수를 오름차순으로 정렬한 리스트

 

 

코드 설명

1. 지도와 방문 여부 초기화

• 입력으로 받은 N×N 크기를 graph라는 2차원 리스트에 저장합니다.
• 각 좌표의 방문 여부를 기록하기 위해 visited라는 2차원 리스트를 만들고, 모든 값을 0으로 초기화합니다.

2. DFS 함수로 단지 크기 계산

• DFS는 특정 좌표에서 시작해, 상하좌우로 연결된 집을 탐색하며 단지 크기를 계산하는 함수입니다.
• 현재 좌표를 방문 처리한 후, count를 1로 초기화하는 이유는 해당 좌표를 단지의 첫 번째 집으로 세는 동시에, 이후 연결된 집들을 하나씩 추가로 세기 위해서입니다. DFS는 각 호출에서 새로운 좌표를 방문할 때마다 그 좌표를 단지 크기에 포함시키므로, count는 호출마다 1로 시작하며, 최종적으로는 호출 횟수만큼 더해져 단지 전체 크기가 계산됩니다. 이는 count가 단지의 크기를 한 단계씩 누적하는 역할을 하기 때문입니다.
   
  상하좌우 네 방향으로 이동하며 연결된 집을 탐색합니다:
  • 이동할 좌표가 지도 범위 안에 있어야 하고(0 <= rx < N, 0 <= ry < N).
  • 방문하지 않았으며(visited[ry][rx] == 0).
  • 집이 있는 경우(graph[ry][rx] == 1).
• 위 조건을 만족하면, DFS를 재귀 호출하여 연결된 집들을 탐색하고, 탐색 결과로 반환된 값을 count에 더합니다.
• 탐색이 끝나면 최종적으로 단지 크기를 반환합니다.

 

3. 전체 지도 순회

• 이중 반복문을 통해 지도 전체를 순회합니다.
• 집이 있고(graph[i][j] == 1), 방문하지 않은 좌표(visited[i][j] == 0)를 발견하면, 이를 새로운 단지의 시작점으로 간주하고 DFS를 호출합니다.
• DFS의 결과(단지 크기)를 lst 리스트에 저장하고, 새로운 단지가 발견되었으므로 단지 수(c)를 1 증가시킵니다.

4. 결과 출력

• 단지 크기를 저장한 lst를 오름차순으로 정렬합니다.
• 총 단지 수(c)와 각 단지 크기를 출력합니다.

단계	현재 좌표 (x, y)	방문 처리	다음 탐색 좌표	DFS 호출 스택 상태	설명
1	(0, 1)	방문 처리	(0, 2), (1, 1)	dfs(0, 1)	첫 번째 집을 발견하고 연결된 집 탐색 시작.
2	(0, 2)	방문 처리	(1, 1)	dfs(0, 1) → dfs(0, 2)	오른쪽으로 이동, 다음 연결된 집 탐색.
3	(1, 1)	방문 처리	(2, 1), (0, 1)	dfs(0, 1) → dfs(0, 2) → dfs(1, 1)	아래로 이동, 연결된 집 계속 탐색.
4	(2, 1)	방문 처리	(2, 0)	dfs(0, 1) → dfs(0, 2) → dfs(1, 1) → dfs(2, 1)	오른쪽으로 이동, 연결된 집 계속 탐색.
5	(2, 0)	방문 처리	- (탐색 종료)	dfs(0, 1) → dfs(0, 2) → dfs(1, 1) → dfs(2, 1) → dfs(2, 0)	더 이상 연결된 집 없음, 재귀 종료.
6	Backtracking	반환	돌아가기	dfs(0, 1) → dfs(0, 2) → dfs(1, 1) → dfs(2, 1)	호출이 끝난 좌표에서 상위 호출로 복귀.
...	Backtracking 계속	반환	돌아가기	dfs(0, 1) → dfs(0, 2)	모든 연결된 집 탐