[BOJ] 일요일 아침의 데이트

https://www.acmicpc.net/problem/1445

1445번: 일요일 아침의 데이트

문제의 지문을 잘 읽어야하는 국어문제입니다. 만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다. 그리고, S와 F는 세지 않는다. 라는 지문의 내용이 있는데 이 부분을 처리하지 않으면 잘못된 답이 나오게 됩니다. S, F인 경우에는 쓰레기에 인접해있지 않는 칸으로 처리하여 해결하면 됩니다.

 

큐에서 빠져나오는 우선순위를 정해주기 위해 우선순위 큐를 사용하여 지나친 쓰레기가 들어있는 칸의 개수, 그 다음으로는 지나친 쓰레기에 인접해있는 칸의 수가 작은 경우가 큐에서 먼저 빠져도록 BFS를 실행해주면 됩니다.

 

import sys, heapq

input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

board = [
    list(input().rstrip())
    for _ in range(n)
]

start = [-1, -1]

# 시작점 찾기
for i in range(n):
    for j in range(m):
        if board[i][j] == 'S':
            start[0] = i
            start[1] = j
            break

    if start[0] != -1 and start[1] != -1:
        break

q = [(0, 0, start[0], start[1])]

dys = [1, 0, -1, 0]
dxs = [0, 1, 0, -1]

def in_range(y, x):
    return 0 <= x < m and 0 <= y < n

visited = [
    [False] * m
    for _ in range(n)
]
visited[start[0]][start[1]] = True

# 근처에 쓰레기가 있는지 판별
def existNearG(y, x):
    for dy, dx in zip(dys, dxs):
        ny = y + dy
        nx = x + dx

        if in_range(ny, nx) and board[ny][nx] == 'g':
            return True

    return False


#O(4nmlog(4nm))
while q:
    passG, nearG, y, x = heapq.heappop(q)
    # 꽃을 만난 경우에는 지나간 쓰레기의 수와 쓰레기와 인접한 칸을 지난 경우를 출력
    if board[y][x] == 'F':
        print(passG, nearG)
        break

    for dy, dx in zip(dys, dxs):
        ny = y + dy
        nx = x + dx

        if in_range(ny, nx) and not visited[ny][nx]:
            visited[ny][nx] = True
            # 쓰레기를 지나가는 경우
            if board[ny][nx] == 'g':
                heapq.heappush(q, [passG + 1, nearG, ny, nx])
            # 칸이 비어있는 경우에는 해당 칸에 인접해있는 쓰레기가 있는지를 더해줌
            elif board[ny][nx] == '.':
                heapq.heappush(q, [passG, nearG + int(existNearG(ny, nx)), ny, nx])
            # S, F인 경우
            else:
                heapq.heappush(q, [passG, nearG, ny, nx])