[Baekjoon/Python] 2667. 단지번호붙이기 (BFS/DFS)

---

문제

NxN 크기의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳을 의미한다.
상하좌우로 연결된 집들을 하나의 단지로 정의할 때,

• 총 단지 수
• 각 단지의 집 개수 (오름차순)

를 구하는 문제이다.

---

요구사항 분석

1. 그래프 탐색 문제로 해석

2차원 배열은 그래프로 볼 수 있으며, 각 칸은 노드가 된다.
상하좌우 이동은 인접 노드 탐색에 해당한다.

2. 연결 요소 문제

연결된 1들의 묶음은 하나의 단지이다.
즉, 이 문제는 “연결 요소의 개수와 크기”를 구하는 문제이다.

---

나의 풀이

1. BFS를 이용한 단지 탐색

• 1을 발견하면 BFS 시작
• 연결된 모든 1을 탐색하며 0으로 변경 (방문 처리)
• 탐색하면서 집 개수를 세어 단지 크기로 저장

from collections import deque

N = int(input())

graph = []
houses = []

for i in range(N):
    graph.append(list(map(int, input())))

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0
    house = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        x, y = queue.pop()

        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]

            if 0 <= tx < N and 0 <= ty < N and graph[tx][ty] == 1:
                queue.append((tx, ty))
                graph[tx][ty] = 0
                house += 1

    return house


for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            houses.append(bfs(i, j))

print(len(houses))
houses.sort()
for house in houses:
    print(house)

---

코드 피드백

1. BFS에서 pop() 사용

x, y = queue.pop()

이 방식은 DFS처럼 동작한다.
BFS를 정확하게 구현하려면 다음과 같이 작성해야 한다.

x, y = queue.popleft()

문제는 풀리지만, 탐색 방식의 의미를 맞추는 것이 중요하다.

---

정석 코드 (BFS + DFS)

1. BFS 풀이

from collections import deque

N = int(input())
graph = [list(map(int, input().strip())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0
    count = 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0
                count += 1

    return count

2. DFS 풀이

def dfs(x, y):
    graph[x][y] = 0
    count = 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
            count += dfs(nx, ny)

    return count

3. 실행 코드

houses = []

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            houses.append(bfs(i, j))  # dfs(i, j)로 변경 가능

houses.sort()

print(len(houses))
for house in houses:
    print(house)

---

풀이 팁 및 정리

1. 연결 요소 문제 패턴

• 1 발견 → 탐색 시작
• 연결된 모든 1 방문 처리
• 개수 카운트

이 패턴은 매우 자주 등장하므로 익혀두는 것이 중요하다.

2. 방문 처리 방법

• visited 배열 사용
• graph 값 직접 변경

이 문제에서는 1 → 0으로 변경하는 방식이 더 간단하다.

3. BFS vs DFS 차이

• BFS → queue.popleft()
• DFS → 재귀 또는 stack

이 문제는 둘 다 가능하지만 구현 방식은 구분해야 한다.

4. map 함수 활용

list(map(int, input()))

문자열을 한 글자씩 나누어 정수로 변환한다.

예: "10101" → [1, 0, 1, 0, 1]

---

마무리

이 문제는 그래프 탐색의 기본인 연결 요소 개념을 연습하기에 적합한 문제이다.
BFS와 DFS 구조, 방문 처리 방식을 확실히 이해하고 넘어가는 것이 중요하다.