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
반응형
'Agorithm > 백준 알고리즘' 카테고리의 다른 글
백준 알고리즘 14248번 점프 점프(python) (0) | 2021.03.14 |
---|---|
백준 알고리즘 15240번 Paint bucket(python) (0) | 2021.03.14 |
백준 알고리즘 18404번 현명한 나이트(python) (0) | 2021.03.14 |
백준 알고리즘 18243번 Small World Network(python) (0) | 2021.03.14 |
백준 알고리즘 18232번 텔레포트 정거장(python) (0) | 2021.03.14 |