[백준] 2667번 단지 번호 붙이기 파이썬(Python) 풀이

 

 

2667번: 단지번호붙이기

[문제]

---

[코드]

 

DFS (깊이 우선 탐색) 풀이

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

graph = []  
result = []
count = 0

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

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


def dfs(x, y):
    global count

    if x < 0 or x >= N or y < 0 or y >= N:
        return

    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)


for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            dfs(i, j)
            result.append(count)
            count = 0
            
result.sort()           
print(len(result))
print(*result, sep='\n')

 

BFS (너비 우선 탐색) 풀이

from collections import deque
import sys
input = sys.stdin.readline
N = int(input())

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

def bfs(graph, x, y):

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

    q = deque()
    q.append((x,y))
    graph[x][y] = 0
    cnt = 1

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

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

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                q.append((nx,ny))
                cnt += 1
    return cnt


c = [bfs(graph, i, j) for i in range(N) for j in range(N) if graph[i][j] == 1]

c.sort()
print(len(c))
print(*c, sep='\n')

---

[해설]

 

백준 - 실버1 단계에 해당하는 '그래프 탐색' 문제이다

이 문제는 깊이 우선탐색, 너비 우선탐색 둘다 접근이 가능한 문제이다

 

매커니즘은 둘다 공통적으로 비슷하나 방식에서 약간 차이가 있다

속도는 너비 우선탐색이 약간더 빠르게 나온다

 

문제 내용은 그렇게 어려운게 아니기 때문에 오늘은 생략하겠다 (귀찮은거 아님)

 

 

문제 핵심 요약

그래프 탐색 - > 전형적인 보드판이 나온다

같은 1 끼리 묶고 이를 count로 저장

이미 다녀간 곳은 방문으로 전환

 

 

그리고 보드 전체를 돌면서 1인경우 dfs, bfs를 실행 - 최종 결과물 저장