[Algo] bfs 연습

기본문제

from collections import deque
​
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
​
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
​
visited = [False] * 9
bfs(graph, 1, visited)

미로탈출

from collections import deque
​
def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    
    while queue :
        x, y = queue.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 >= m:
                continue
            
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    
    return graph[n-1][m-1]
​
n, m = map(int, input().split())
​
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
​
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
​
print(bfs(0, 0))
​

백준 2667 단지 번호 붙이기

import sys
from collections import deque
input = sys.stdin.readline
​
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
​
def bfs(graph, a, b):
    queue = deque() 
    queue.append([a, b])
    graph[a][b] = 0 
    count = 1 
    
    while queue:
        x, y = queue.popleft() 
        graph[x][y] = 0
        for i in range(4):  
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= len(graph) or ny < 0 or ny >= len(graph):
                continue
            if graph[nx][ny] == 1: 
                graph[nx][ny] = 0  
                queue.append([nx, ny]) 
                count += 1  
    return count
​
N = int(input())
graph = [] 
result = []
for _ in range(N):
    graph.append(list(map(int, input().rstrip())))
​
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            count = bfs(graph, i, j)
            result.append(count)
result.sort()
print(len(result)) 
for k in result: 
    print(k)