[백준 1445번] 파이썬 - 일요일 아침의 데이트

백준 1445 - 일요일 아침의 데이트

시간 제한 2초, 메모리 제한 128MB

# 조건

• 일요일 아침에 형택이는 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는 반드시 하나만 주어진다.

출력

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

# 접근 방법

• 다익스트라를 이용하여 풀어주면 된다.
• dist 배열은 크기가 2인 1차원 배열을 arr 크기만큼 만들어준다.
• 0번 인덱스는 쓰레기를 지나간 횟수, 1번 인덱스는 쓰레기 옆을 지나간 횟수로 해준다.
• 이후 방문 시 쓰레기를 지나간 횟수가 적거나, 쓰레기를 지나간 횟수가 같은데 쓰레기 옆을 지나간 횟수가 적다면 갱신하고, heappush 해준다.
• 이 때 주의할 점은, 출발지와 도착지에서는 옆에 쓰레기가 있더라도 카운트를 해주지 않아야 한다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  

def dijkstra(si, sj, ei, ej):  
    q = []  
    q.append((0, 0, si, sj))  
    while q:  
        cnt, side, qi, qj = heappop(q)  
        if dist[qi][qj][0] < cnt:  
            continue  
        if (qi, qj) == (ei, ej):  
            if dist[qi][qj][0] == cnt:  
                dist[qi][qj][1] = min(dist[qi][qj][1], side)  
            continue  
        for d in range(4):  
            ni, nj = qi+di[d], qj+dj[d]  
            if 0<=ni<N and 0<=nj<M:  
                v, s = cnt, side  
                if arr[ni][nj] == 'g':  
                    v = cnt + 1  
                else:  
                    if arr[ni][nj] == '.':  
                        for d in range(4):  
                            ci, cj = ni+di[d], nj+dj[d]  
                            if 0<=ci<N and 0<=cj<M and arr[ci][cj] == 'g':  
                                s += 1  
                                break  

                if dist[ni][nj][0] < v:  
                    continue  
                else:  
                    if dist[ni][nj][0] == v:  
                        if dist[ni][nj][1] > s:  
                            dist[ni][nj][1] = s  
                            heappush(q, (v, s, ni, nj))  
                    else:  
                        dist[ni][nj] = [v, s]  
                        heappush(q, (v, s, ni, nj))  
    return dist[ei][ej][0], dist[ei][ej][1]  


N, M = map(int, input().split())  
arr = [list(input().strip()) for _ in range(N)]  
dist = [[[float('inf'), float('inf')] for _ in range(M)] for _ in range(N)]  
si, sj, ei, ej = 0, 0, 0, 0  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 'S':  
            si, sj = i, j  
        elif arr[i][j] == 'F':  
            ei, ej = i, j  
dist[si][sj] = [0, 0]  
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
print(*dijkstra(si, sj, ei, ej))