[Python] BOJ/백준 2667번 단지번호붙이기

[문제]

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

2667번: 단지번호붙이기

 

[풀이]

🔥 DFS vs BFS

✨ DFS, BFS 모두 적합한 유형

• 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우

✨ DFS가 적합한 유형

• 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음)
• 경로의 특징을 저장해둬야 하는 문제
  • ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제
• BFS는 경로의 특징을 가지지 못함

✨ BFS가 적합한 유형

• 미로찾기 등 최단거리를 구해야 할 경우
• DFS는 처음으로 발견되는 해답이 최단거리 라는 것 보장 X
• 반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.

---

해당 문제는 DFS, BFS 모두 가능한 문제이다. 왜냐?.. 위에 설명한 것처럼 모든 정점을 방문해야 하기 때문

 

1️⃣ BFS 풀이

1. graph 전체를 돌면서 값이 1인 지점부터 bfs 탐색을 시작한다.
2. 집이 있는 곳을 탐색했을 경우 다시 방문하면 안되기 때문에 값을 -1로 바꿔준다.
3. bfs 함수가 끝나 return 되면 단지 하나를 다 돌은 것이다.
4. 다시 1로 돌아가 값이 1인 지점부터 탐색을 다시 시작한다.

 

[코드]

import sys
from collections import deque

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
    
def bfs(graph, a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = -1

    house_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:
                if graph[nx][ny] == 1:
                    house_count += 1
                    queue.append((nx, ny))
                    graph[nx][ny] = -1
    return house_count


n = int(sys.stdin.readline())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline()[:-1])))

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

house_list.sort()
print(len(house_list))
for cnt in house_list:
    print(cnt)

 

2️⃣ DFS 풀이

bfs에서는 큐를 사용했지만 dfs는 재귀를 이용해서 탐색한다.

 

아파트 단지 내의 첫 번째 아파트만 dfs 함수를 호출해도 한 단지 내에서는 재귀로 계속 dfs를 호출해 방문한 곳은 graph를 -1로 갱신한다.

따라서 메인 함수에서 dfs(i, j)가 True일 경우 해당 아파트가 포함된 단지를 모두 돈 것이기 때문에 house_list에 house_count를 추가해준다.

 

[코드]

import sys

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

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global house_count
        house_count += 1
        graph[x][y] = -1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False


n = int(sys.stdin.readline())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline()[:-1])))

house_list = []
house_count = 0
for i in range(n):
    for j in range(n):
        if dfs(i, j):
            house_list.append(house_count)
            house_count = 0

house_list.sort()
print(len(house_list))
for cnt in house_list:
    print(cnt)