백준 / 쉬운 최단거리 / 14940번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 쉬운 최단거리 / 14940번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/14940
 

문제 설명

---

나의 풀이

from collections import deque

def bfs(tile, visit):
    q = deque()

    # 상하좌우로 움직여야함
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    b = False
    for i in range(len(tile)):
        for j in range(len(tile[i])):
            # 2 찾으면 종료 시킬 반복문
            if tile[i][j] == 2:
                q.append((i, j, 1))
                tile[i][j] = 0
                visit[i][j] = True
                b = True
                break
        if b:
           break

    while q:
        y, x, distance = q.popleft()

        for iy, ix in move:
            ny = iy + y
            nx = ix + x
            if 0 <= ny < len(tile) and 0 <= nx < len(tile[0]):
                if tile[ny][nx] == 1 and not visit[ny][nx]:
                    tile[ny][nx] = distance
                    visit[ny][nx] = True
                    q.append((ny, nx, distance + 1))

    for i in range(len(tile)):
        for j in range(len(tile[i])):
            if not visit[i][j] and tile[i][j] == 1:
                tile[i][j] = -1

n, m = map(int, input().split())

tile = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

bfs(tile, visited)

for t in tile:
    for i in t:
        print(i, end = ' ')
    print()

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/77

[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)