[백준(BOJ)] 2667번 : 단지번호 붙이기 - Python(파이썬) - (실버1, BFS DFS)

풀이

BFS로도 DFS로도 풀 수 있는 문제이다.

연결요소 유형이고, 방문했을 때, 방문한 곳을 0으로 바꿔준다는게 핵심이다!

지금도 자꾸 함수를 외워서, 그리고 아주조금 생각하면서 풀고 있는데, 흰 종이를 가져와 그래프를 그림과 표로
방문해준 곳을 어떻게 방문표시를 해줄건지 생각하며 풀어보자.

 

BFS로 풀기

from collections import deque

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

def bfs(graph, x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0    
    cnt = 1
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue

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

    return cnt

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

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

array.sort()

print(len(array))

for i in array:
    print(i)

 

DFS로 풀기

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

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

def dfs(x, y):
    
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    
    if graph[x][y] == 1:
        global cnt
        cnt += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False
        
cnt = 0
result = 0
array = []
for i in range(n):
    for j in range(n):
        if dfs(i, j) == True:
            array.append(cnt)
            result += 1
            cnt = 0

array.sort()
print(result)
for i in range(len(array)):
    print(array[i])