[백준] 4485 파이썬

문제

---

• 백준 4485 (골드 4)

백준 4485

젤다의 게임을 안해봐서 도둑루피는 무슨 말인지 잘 몰랐는데 뭔가 말을 어렵게 써놓은 느낌이다.
요약하자면 그래프를 탐색하면서 (0, 0)부터 (n-1, n-1)까지의 최소 가중치를 찾는 문제였다.
다익스트라 알고리즘을 사용하면 해결 가능한 문제였다.

다익스트라 알고리즘

---

• 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• for문과 Heap을 사용해서 구현 가능한데 노드의 개수가 많아지면 Heap을 사용해야 한다.
• 알고리즘의 아이디어는 아래와 같다.
  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 최대값으로 초기화한다.
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  4. 해당 노드를 거쳐 다른 노드로 가능 비용을 계산하여 최단 거리 테이블을 갱신한다.
  5. 위 과정에서 3번과 4번을 반복한다.
• Heap을 통해서 구현한 파이썬 코드는 아래와 같다.

import heapq
import sys
input = sys.stdin.readline
 
n,m = map(int, input().split())
st = int(input())
graph = [[] for i in range(n+1)]
distance = [10**9]*(n+1)
 
for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))
 
def dijkstra(st):
    q=[]
    heapq.heappush(q, (0, st))
    distance[st]=0
    while q:
        weight, now = heapq.heappop(q)
        if distance[now] < weight:
            continue
        for i in graph[now]:
            dist = weight + i[1]
            if dist < distance[i[0]]:
                distance[i[0]] = dist
                heapq.heappush(q, (dist, i[0]))
 
dijkstra(st)
 
if distance[n] != 10**9:
    print(distance[n])
else:
    print("INF")

내 코드

---

다익스트라 알고리즘을 떠올리지 못하고, dfs 혹은 bfs로 풀 수 있을 것 같아서 시도해보았다.
우선적으로 dfs로 구현해보았는데 시간 초과가 발생했다.
모든 경로를 탐색하면 시간초과가 발생하는 것 같아서 bfs를 통해서 각 노드에서의 최소 가중치를 갱신해가면서 구하는 방식으로 변경하였다.

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

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

def bfs():
    queue=deque()
    queue.append([0,0])
    visited[0][0]=cave[0][0]
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if visited[y][x] + cave[ny][nx] < visited[ny][nx]:
                    visited[ny][nx] = visited[y][x] + cave[ny][nx]
                    queue.append([nx, ny])

    return visited[n-1][n-1]

while True:
    n = int(input())
    cnt += 1
    if n == 0:
        exit()

    cave = [list(map(int, input().split())) for _ in range(n)]
    visited = [[10**9] * n for _ in range(n)]
    print("Problem " + str(cnt) + ":", bfs())

다익스트라 알고리즘을 잘 알지 못했는데 최단 경로 문제를 만나게 된다면 사용해 봐야겠다.