BOJ 백준 14940번 쉬운 최단거리 | Python
🔎 문제 설명
🩶 실버 1
- 난이도 ★☆☆☆ - 그래프탐색
최단거리를 구하는 방법엔 다양한 알고리즘이 있지만, 역시 난 가장 익숙한 BFS로 풀었다.
이 문제는 최단거리 찾는 유형 중 기본 유형에 속한다. 방문여부를 저장하는 visited 에 거리를 함께 저장했다. 백준 특정 거리의 도시 찾기 문제와 상당히 유사하다. 이전에 접했던 문제라면 역시 어렵지 않다.
📌 문제 풀이 큰 틀
2찾아서 시작점 위치 찾기- BFS로 가장 가까운 노드부터 최단거리를 계산
visited에 거리를 1씩 더해 ‘첫 도시 ~ 현재 도시’의 거리를 계산
💻 내 코드
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
goal = (-1,-1)
graph = []
for i in range(n):
tmp = list(map(int, input().split()))
graph.append(tmp)
if 2 in tmp:
goal = (i, tmp.index(2))
# 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표지점
def bfs(goal):
visited = [[-1 for _ in range(m)] for _ in range(n)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
queue = deque([goal])
x, y = goal
visited[x][y] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0<=nx<n and 0<=ny<m:
if not graph[nx][ny]:
# graph 값이 0이면 visited 값을 0으로 바꿔줌
visited[nx][ny] = 0
elif graph[nx][ny] == 1 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
queue.append((nx,ny))
return visited
visited = bfs(goal)
# 첫 번째 출력 시도 -> 틀림
# for i in range(n):
# print(*visited[i])
# 두 번째 출력 시도 -> 맞음
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
print(0, end = ' ')
else:
print(visited[i][j], end = ' ')
print()
🤷♀️ 예외 케이스?
사실 첫 번째 출력 시도로 했을 때 예외가 생기는 케이스를 아직 찾진 못했다. 혹시 이 글을 접하는 코딩 고수님이 있다면 질문 게시판/(예외케이스) 마지막 출력문을 살짝 바꾸면 … 에 답변 부탁드립니다 🙇♀️
2024.05.16 기준 코딩 고수님의 댓글을 확인했다! 방문하지 못하는 곳이 있을 수 있다는 것이다. 그래서 첫 번째 출력 시도처럼 그냥 visited를 출력하게 되면 0이어야 할 부분이 -1로 출력된다. 초기값을 0으로 바꾸자니 다른 visited 값에 -1씩 해줘야 해서 그냥 두 번째 출력 코드로 진행하는 것이 좋을 것 같다.
5 5
2 1 1 1 1
1 1 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).