[백준/파이썬]14940 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

문제

백준 14940번 쉬운 최단거리

BFS공부 후에 처음으로 BFS응용? 문제를 풀어 봤다.

 

백준 14940 쉬운 최단거리 입출력 예제

나의 문제 접근 방법은 지도에서 2가 나온 지점을 시작 지점으로 근처에 갈 수 있는 index번호들을 큐에 하나씩 넣어가며 탐색했다.

 

예시로

0, 0에서 갈 수 있는 index들은 [0,1], [1,0]이 있다.

[0,1]에서 갈 수 있는 index들은 [0, 2], [1, 1]이 있고

[1,0]에서 갈 수 있는 index들은 [1,1], [2, 0]이 있지만 [1,1]은 [0,1]에서 먼저 방문했으므로 [1,1]만 방문 가능 하다

 

이런 식으로 주변에 갈 수 있는 index번호들을 큐에 넣어서 BFS탐색을 하면 된다.

 

각 방문 지점 카운팅 방법은

 

방문 지점 이전의 값에 1을 더해주면 된다.

 

정답

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

def bfs(index) :
    queue = deque()
    queue.append(index)

    visit[index[0]][index[1]] = 1

    while queue :
        y, x = queue.popleft()
        for i in range(4) :
            new_x = x+dx[i]
            new_y = y+dy[i]
            if new_x < 0 or new_y < 0 or new_x >= m or new_y >= n or map_[new_y][new_x] == 0:
                continue
            else :
                if visit[new_y][new_x] == 0 :
                    visit[new_y][new_x] = 1
                    ans[new_y][new_x] = ans[y][x]+1
                    queue.append([new_y, new_x])

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

map_ = []
for i in range(n) :
    map_.append(list(map(int, input().split())))

ans = [[0 for _ in range(m)] for _ in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]

is_break = False
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
for i in range(n) :
    for j in range(m) :
        if map_[i][j] == 2 :
            start_idx = [i, j]

            is_break = True
            break
    if is_break :
        break

bfs(start_idx)


for i in range(n) :
    for j in range(m) :
        if map_[i][j] == 1 and visit[i][j] == 0 :
            ans[i][j] = -1
            

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

 

 

항상 이런 문제 풀 때마다 Row, Column 인덱싱이 헷갈려서 몇 번씩 수정한다 ㅜ