[백준14940] / 쉬운 최단거리 - 그래프(BFS)

백준14940

 

 

푼 날짜 : 2024.07.25

푼 문제 : [14940] / 쉬운 최단거리

사용한 언어 : python

 

 

푼 방법 :

너비 우선 탐색으로 접근하였다.

 

원래 갈 수 없는 땅인 위치는 0을 출력하고,
원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력

 

 

처음에는 리스트 형식( [1, 2, 3, ~] )으로 출력을 잘못해서 틀렸고, 

두 번째에는 위의 예외처리를 안해줘서 틀렸다.

 

 

항상 문제를 꼼꼼하게 읽자!

 

 

 

코드 :

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph_ = []
visited = [[0 for _ in range(M)] for _ in range(N)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def BFS(graph_, visited, v):
    queue = deque([(v)])
    visited[v[0]][v[1]] = 0

    while queue:
        now = queue.popleft()

        for i in range(4):
            py, px = now[0]+dy[i], now[1]+dx[i]
            if 0<=py<N and 0<=px<M:
                if not visited[py][px] and graph_[py][px] == 1:
                    queue.append((py, px))
                    visited[py][px] = visited[now[0]][now[1]] + 1

x, y = 0, 0
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(len(row)):
        if row[j] == 2:
            y = i
            x = j
    graph_.append(row)

BFS(graph_, visited, (y, x))

for i in range(N):
    for j in range(M):
        if graph_[i][j] != 0  and visited[i][j] == 0: 
            visited[i][j] = -1

visited[y][x] = 0 # 시작점 0처리

for i in range(N):
    for j in range(M):
        print(visited[i][j], end=' ')
    print()

 

 

"원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력"

해당 부분 처리를 해주면서 시작지점이 -1이 되었기에 바로 다시 시작점을 0 처리 해주었다.

 

 

이젠 웬만한 그래프 문제는 다 풀 수 있게 되었다! ৻(≧ᗜ≦৻)

블로그도 열심히 작성해야지!