SWEA 1249 보급로 (파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

---

풀이 (다익스트라)

from heapq import heappop, heappush

for tc in range(1, int(input())+1):
    N = int(input())
    maps = [list(map(int, input())) for _ in range(N)]

    # 다익스트라로 최단 거리 구하기
    visit = [[0]*N for _ in range(N)]
    D = [[0xffffff]*N for _ in range(N)]
    D[0][0] = 0

    # 우선순위큐를 사용하기 위해 heapq사용
    Q = []
    heappush(Q, (0, 0, 0))  # (거리, r, c)

    while Q:
        d, r, c = heappop(Q)
        # 방문 확인 작업
        if visit[r][c]: continue
        visit[r][c] = 1

        for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < N and D[nr][nc]:
                # 간선 완화 작업
                if D[nr][nc] > D[r][c]+maps[nr][nc]:
                    D[nr][nc] = D[r][c] + maps[nr][nc]
                    heappush(Q, (D[nr][nc], nr, nc))

    print(f'#{tc}', D[N-1][N-1])

 

 

---

풀이 (다익스트라_dist 딕셔너리 사용)

from heapq import heappop, heappush
from collections import defaultdict

for tc in range(1, int(input())+1):
    N = int(input())
    maps = [list(map(int, input())) for _ in range(N)]

    dist = defaultdict(int)
    
    Q = []
    heappush(Q, (0, 0, 0))  # (거리, r, c)

    while Q:
        d, r, c = heappop(Q)

        if (r, c) not in dist:
            dist[(r, c)] = d
            for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                nr, nc = r+dr, c+dc
                if 0 <= nr < N and 0 <= nc < N:
                    alt = d + maps[nr][nc]
                    heappush(Q, (alt, nr, nc))

    print(f'#{tc}', dist[(N-1, N-1)])

 

 

---

풀이 (BFS)

for tc in range(1, int(input())+1):
    N = int(input())
    maps = [list(map(int, input())) for _ in range(N)]

    #BFS로 최단 거리 구하기
    D = [[0xffffff]*N for _ in range(N)]
    D[0][0] = 0
    Q = [(0, 0)]

    while Q:
        r, c = Q.pop(0)
        for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < N and D[nr][nc] > D[r][c]+maps[nr][nc]:
                D[nr][nc] = D[r][c] + maps[nr][nc]
                Q.append((nr, nc))

    print(f'#{tc}', D[N-1][N-1])

 

---

후기

• 실행시간 순서 대로 297 ms, 644 ms, 253 ms 
• 흠.. 왜 bfs가 가장 빠르지??
• 뭐 bfs랑 다익스트라 방법1은 비슷하니 그렇다 치고, 다익스트라 딕셔너리를 사용한 것은 왜 느리지..?
• 잘 모르겠다...