728x90
반응형

기본적인 BFS 문제이다. 처음에 '1'의 위치들을 queue에 모두 추가해놓고 bfs를 돌리면 쉽게 풀 수 있다.

간단하지만 여태까지 풀어왔던 문제랑 조금 느낌이 달라서 푸는데 시간이 조금 걸렸다.

from collections import deque

def bfs():
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < n) and (0 <= X < m) and graph[Y][X] == '0':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == '1':
            graph[i][j] = 0
            q.append((i, j))
bfs()
for line in graph:
    print(*line)
728x90
반응형

+ Recent posts