[백준/파이썬] 14940번

📍백준 14940 문제

https://www.acmicpc.net/problem/14940

코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
graph = []
visited = [[False for _ in range(m)]for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            x, y = i, j
que = deque()
que.append((x, y))
visited[x][y] = True
graph[x][y] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False:
            if graph[nx][ny] == 1:
                visited[nx][ny] = True
                graph[nx][ny] = graph[x][y]+1
                que.append((nx, ny))
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visited[i][j] == False:
            graph[i][j] = -1

for i in range(n):
    for j in range(m):
        print(graph[i][j], end=" ")
    print()

풀이

BFS로 풀어주면 된다.
만약 que에 아무것도 들어있지 않다면, 이중반복문을 통해 원래 갈 수 있는 땅 중, 가지못한 땅을 찾는다.

• graph[i][j] == 1 and visited[i][j]==False 이라면, graph[i][j]의 값을 -1로 바꿔준다.