[BOJ/백준] 1445 일요일 아침의 데이트

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split())



INF = float('inf')
step_trash = [[INF for _ in range(M)] for _ in range(N)]
arround_trash = [[INF for _ in range(M)] for _ in range(N)]

arround_trash_can = [[0 for _ in range(M)] for _ in range(N)]


arr = []
start = []
flower = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'S':
            start = (x,y)
        elif temp[y] == 'F':
            flower = (x,y)
    
    arr.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]


for x in range(N):
    for y in range(M):
        if arr[x][y] == 'g':
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        arround_trash_can[nx][ny] = 1

node_list = []

heapq.heappush(node_list,(0,0,start[0],start[1]))

step_trash[start[0]][start[1]] = 0
arround_trash[start[0]][start[1]] = 0
visited = [[True for _ in range(M)] for _ in range(N)]

while node_list:
    s_t,p_t,x,y = heapq.heappop(node_list)

    if not visited[x][y]:
        continue
    visited[x][y] = False


    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] == 'g':
                if step_trash[nx][ny] > s_t + 1:
                    step_trash[nx][ny] = s_t + 1
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny], arround_trash[nx][ny], nx, ny))
            else:
                if step_trash[nx][ny] > s_t:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] = p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))
                elif step_trash[nx][ny] == s_t and arround_trash[nx][ny] > p_t + arround_trash_can[nx][ny]:
                    step_trash[nx][ny] = s_t
                    arround_trash[nx][ny] =  p_t + arround_trash_can[nx][ny]
                    heapq.heappush(node_list,(step_trash[nx][ny],arround_trash[nx][ny],nx,ny))






x,y = flower

print(step_trash[x][y] , arround_trash[x][y])

이 문제를 지문을 이해하는데 어려움을 겪었던 문제였다. 

 

문제를 제대로 읽어야하는데 빈 공간을 갈때 주변의 쓰레기 개수와 상관없이 1개이든 4개이든 1번의 불쾌함으로 측정을 해야한다.

 

그러므로 이 점을 주의해서 우선순위를 설정을 해서 다익스트라를 해줘야한다.

 

다익스트라를 돌리기전에 사전 작업을 했는데, 쓰레기인 구역을 찾아서

 

그 주변에 빈공간이 있으면 arround_trash_can라는 배열에 1로 표시를 해줬다.

 

그래서 arround_trash_can이라는 배열에 0이 아닌 1이 표시된 부분은 쓰레기가 존재하는 옆칸을 지나가는 것이다.

 

이 문제에서 형택의 여자친구는 쓰레기를 지나가는 것을 가장 싫어하고, 쓰레기 옆을 지나가는 것을 두번째로 싫어한다고 되어있다.

 

그러므로 heapq에 우선순위를 쓰레기를 지나가는 것 s_t를 가장 앞에 두었고, 쓰레기 옆을 지나가는 개수인 p_t를 두번째 인자로 넣어주었다.

 

이렇게 한뒤 형택이 상하좌우로 움직이면서 쓰레기인 칸을 밟았을때에는 step_trash의 값과 비교를 해서 더 낮은 값이면, 갱신을 하고 넣어주었다.

 

그리고 빈공간일때에는 먼저 쓰레기를 밟는 개수가 더 작은 경우인지 확인을 한 뒤, 더 작으면 값을 갱신하고 heapq에 넣어준다.

 

근데 그게 아니라 쓰레기를 밟는 개수는 동일하다면, 쓰레기 옆을 지나간 횟수를 비교를 해서 heapq에 넣어준다.

 

이 문제에서 주의해야했던 점은 쓰레기 옆을 지나가는 유무를 구분하는 것이지, 빈공간 옆의 쓰레기의 개수를 세는

 

것이 아니였던 점이다.