[일요일 아침의 데이트/G2/Python3]

1445번 일요일 아침의 데이트

 

문제
일요일 아침에 형택이는 Maroon5의 Sunday Morning이란 노래를 들으면서 여자친구와의 로맨틱한 여행을 떠나기로 했다. 형택이는 이것저것 환상에 빠져있다가, 계획을 세우는데 실패했다. 따라서, 주위에 있는 숲을 같이 탐험하기로 했다. 깊은 숲 속에는 정말 아름다운 꽃이 하나 있다. 형택이는 여자친구의 마음을 감동시키기 위해서, 꽃을 보여주면서 자신의 마음을 전해주려고 급하게 계획했다. 불행하게도, 사람들이 숲에다 쓰레기를 버려서 형택이의 계획은 정말 망가지기 직전이다. 형택이는 그동안 여자친구와 사귀면서 2가지 깨달은 것이 있는데, 한 가지는 쓰레기를 통과해서 지나가는 것을 정말 싫어하는 것이고, 쓰레기를 따라 옆을 지나가는 것도 정말 불편하게 느낀다는 것이다. 형택이는 방금 쓰레기가 어디에 있는지 조사를 마쳤다. 입력으로 숲의 지도가 주어진다. S는 형택이와 여자친구의 데이트 시작장소를  나타내고, F는 꽃이 있는 위치를 나타내고, g는 쓰레기가 있는 위치를 나타낸다. 그리고. 은 아무것도 없는 깨끗한 칸이다. 형택이의 목표는 S에서 F까지 가는데, 쓰레기로 차있는 칸을 되도록이면 적게 지나가는 것이다. 형택이와 여자친구는 한 번에 한 칸 움직일 수 있다. 가로 or 세로로 한 칸 움직일 수 있다. 만약 되도록 적게 지나가는 경우의 수가 여러 개라면, 쓰레기 옆을 지나가는 칸의 개수를 최소로 해서 지나려고 한다. 만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다. 그리고, S와 F는 세지 않는다.

입력
첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다.
둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있다. S는 반드시 모서리에 위치해 있고, F는 모서리에 위치해있지 않다. 그리고 S와 F는 반드시 하나만 주어진다.

출력
첫째 줄에 형택이와 여자친구가 가장 최적의 방법으로 숲을 지났을 때, 지나가는 쓰레기의 최소 개수를 출력하고, 공백으로 구분한 후에 쓰레기 옆을 지나가는 칸의 개수를 출력한다.

그래프 이론, 최단 경로, 데이크스트라

 

데이크스트라를 통해 풀이가 가능하다.

쓰레기를 밟거나 지나간 경로는 우선순위를 낮추는 방식으로 풀이하였다.

 

조건의 처리가 생각보다 이해가 안 가서 어려웠다.

쓰레기를 통과한 경우, 옆을 지나간거는 카운트하지 않는다. S와 F일 때도 판단하지 않는다.

 

 

import sys
import heapq

col, row = map(int, sys.stdin.readline().split())
visit = [[False] * row for _ in range(col)]

maze = [list(sys.stdin.readline().rstrip()) for _ in range(col)]

hq = []
f_y, f_x = 0, 0

move_list = [[0,1],[0,-1],[1,0],[-1,0]]
check_list = [[-1,1],[-1,0]]
def find_near_garbage(y, x):
    for ay, ax in move_list:
        dy, dx = ay+y, ax+x
        if dy<0 or dx<0 or dy>=col or dx>=row: continue
        if maze[dy][dx] == 'g': return True
    return False

for i in range(col):
    for j in range(row):
        if maze[i][j] == 'S':
            hq.append((0, 0, i, j))
        if maze[i][j] == 'F':
            f_y, f_x = i, j

while hq:
    g_time, g_near_time, y, x = heapq.heappop(hq)
    if visit[y][x]: continue
    visit[y][x] = True
    if y == f_y and x == f_x:
        print(g_time, g_near_time)
        break
    
    for ay, ax in move_list:
        dy, dx = y+ay, x+ax
        if dy<0 or dx<0 or dy>=col or dx>=row: continue
        if visit[dy][dx]: continue
        if maze[dy][dx] == 'g':
            heapq.heappush(hq, (g_time+1, g_near_time, dy, dx))
            continue
        if maze[dy][dx] == 'F':
            heapq.heappush(hq, (g_time, g_near_time, dy, dx))
            continue
        heapq.heappush(hq, (g_time, g_near_time + (1 if find_near_garbage(dy, dx) else 0), dy, dx))​

 

---