#1445 일요일 아침의 데이트

일요일 아침의 데이트는 다익스트라 알고리즘을 이용하는 문제로 Gold II 문제로 잡혀 있습니다.

 

아침에 산책을 하면서 야외에서 커피를 같이 마시면 즐겁겠죠?

다익스트라 알고리즘을 알고 있는 분들은 어렵지 않게 풀 수 있습니다.

 

일단 맵을 읽으면, 이 맵을 적절하게 변환을 해주었습니다.

 

예제와 같이 입력이 주어진다면,

6 6
......
g..F..
......
..g...
......
...S.g

저는 이 입력을 다음과 같은 형태로 변환을 했습니다.  쓰레기가 있는 주변을 1로 만들고, 쓰레기는 10,000의 값으로 채웠습니다.  S, F는 세지 않는다고 했으니, 추후에 그 부분은 다시 0의 값으로 만들고요.

1	0	0	0	0	0
10K	1	0	0	0	0
1	0	1	0	0	0
0	1	10K	1	0	0
0	0	1	0	0	1
0	0	0	0	1	10K

위의 형태로 맵을 바꾸면, 한칸 움직일때마다 맵의 값을 읽어서 경로값을 추가하는 형태로 작성을 했습니다.

 

이번 문제는 파이썬3을 이용해서 작성을 했는데요.  일단 heapq 모듈이 min heap이라서 해당부분을 사용한 이유가 많습니다.  C++의 priority queue를 적절하게 cmp함수를 작성해서 사용하셔도 무난합니다.

 

쓰레기가 있는 위치의 값을 10,000으로 설정한 이유는 총 칸의 수가 50x50을 넘지않기 때문이었고, 모두 쓰레기 근처의 값이라고 해도 2,500을 넘지 않으니 10,000 값은 충분한 값이 됩니다.

 

평범한 다익스트라 알고리즘을 변형하여 사용했습니다.  A* 알고리즘을 사용해도 되겠지만, 예측값 자체가 크게 의미가 없어서 사용하지 않았습니다.  다익스트라 알고리즘은 도착점이 없지만, 제가 푼 경우는 도착점에 도달하면 바로 프로그램을 종료하도록 하였습니다.  다익스트라 알고리즘은 방문한 노드의 값은 최종값으로 더이상 변경이 되지 않기때문에 도착점을 방문하게 되면 더 이상 작업은 무의미합니다.

 

아래는 제가 작성한 파이썬 코드입니다.  코드는 참조용으로만 봐주세요.

 

"""
    baekjoon #1445 - Sunday date
        - by Aubrey Choi
        - created at 2022-08-09
"""
from heapq import *
Infty = 100000000
n, m = map(int, input().split())
maps = [[0]*m for _ in range(n)]
drc = ( (-1, 0), (0, -1), (1, 0), (0, 1) )

for i in range(n):
    line = input()
    for j in range(m):
        c = line[j]
        if c == 'S': start = (i, j)
        elif c == 'F': finish = (i, j)
        elif c == 'g':
            maps[i][j] = 10000
            for dr, dc, in drc:
                r, c = i+dr, j+dc
                if r < 0 or r >= n or c < 0 or c >= m or maps[r][c] != 0:
                    continue
                maps[r][c] = 1

maps[start[0]][start[1]] = 0
maps[finish[0]][finish[1]] = 0
values = [ [Infty]*m for _ in range(n) ]
visited = [ [False]*m for _ in range(n) ]
heap = []
heappush(heap, (0, start))
while True:
    score, u = heappop(heap)
    if visited[u[0]][u[1]]: continue
    if u == finish: break
    visited[u[0]][u[1]] = True
    for dr, dc in drc:
        r, c = u[0]+dr, u[1]+dc
        if r < 0 or r >= n or c < 0 or c >= m or visited[r][c]: continue
        if values[r][c] > score + maps[r][c]:
            values[r][c] = score + maps[r][c]
            heappush(heap, (values[r][c], (r, c)))
v = values[finish[0]][finish[1]]
print(v//10000, v%10000)