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

0.  문제 링크

 

 

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

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

---

1.  풀이 방법

 

 

문제를 보자마자 BFS로 풀려고 했다.

여기서 키포인트는 비어있는 칸에 방문했는데, 근처에 쓰레기가 있다면 해당 비어있는 칸을 다른 어떤 값으로 변경해줘야 한다.

아 그리고 문제를 잘 읽어야 한다. 처음에 문제 잘못 읽어서 조금 고생했음

 

풀이 방법은 비교적 쉽다. 비슷한 류의 문제를 풀어서 그런가 쉽게 느껴졌음

왜냐면 최적의 조건이 딱 명확하기 때문이다. 보통 bfs는 먼저 도착하는 것을 최적의 조건으로 삼는 경우가 많은데, 이번에는 밟고 지나가는 쓰레기의 개수와 인접한 쓰레기의 개수를 최적의 조건으로 세웠기 때문에 그에 맞춰 구현하면 된다.

어떤 좌표에 갈 때까지 밟고 지나온 쓰레기의 개수와 인접한 쓰레기가 있는 비어있는 칸의 개수를 세는 맵 두 개를 추가로 구현했다.

참고로 이 두 개의 맵은 처음에 시작점을 제외하고 2500으로 초기화했다. (문제에서 최대 50 * 50 크기의 맵이 나오기 때문!)

뭐 이렇게 해서 조건을 세워서 하면 쉽게 풀린다.

 

근데 이 문제를 BFS에 heapq로 풀거나, 다익스트라로 풀면 얘기가 좀 달라진다.

일단 힙을 쓰면 쓰레기의 개수와 인접한 쓰레기의 개수로 판단해야 하고, 다익스트라로 한다면 맵의 비용을 좀 변경해야 한다.

물론 그 방법이 더 빠르겠지만 귀찮아서 안 하고, 그냥 BFS로 풀었다.

 

여러분은 다양한 방법으로 풀어보십시오!

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


def sol(flag):
    # 다음 위치의 값과 현재 위치를 비교함
    i, j = ((0, 0), (1, 0), (0, 0), (0, 1))[flag]       # 현재 위치에 쓰레기, 인접한 곳에 쓰레기

    if ct[ny][nx] < ct[y][x] + i:
        return False  # 이전 + i이 가려는 곳보다 크면 갈 필요 없음

    elif ct[ny][nx] == ct[y][x] + i:  # 만약 같다면?
        if cat[ny][nx] <= cat[y][x] + j: return False  # 가려는 곳보다 이전이 같거나 크면 갈 필요 없음

    ct[ny][nx] = ct[y][x] + i
    cat[ny][nx] = cat[y][x] + j

    if flag:
        dq.append([ny, nx])

    return True


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [list(input().strip()) for _ in range(n)]
    ct = [[2500] * m for _ in range(n)]        # check trash
    cat = [[2500] * m for _ in range(n)]       # check adjacent trash
    dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    dq = deque()

    for y in range(n):
        for x in range(m):
            match maps[y][x]:
                case 'S':
                    dq.append([y, x])
                    ct[y][x] = cat[y][x] = 0

                case 'F':
                    out_y, out_x = y, x

                case '.':
                    for dy, dx in dir:
                        ny, nx = y + dy, x + dx
                        if 0 <= ny < n and 0 <= nx < m:
                            if maps[ny][nx] == 'g':     # 쓰레기 근처를 지날때 maps[y][x]를 a로 변경함
                                maps[y][x] = 'a'
                                break

    while dq:
        y, x = dq.popleft()

        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                match maps[ny][nx]:
                    case 'g':     # 쓰레기를 밟을 때
                        if not sol(1): continue

                    case '.':       # 땅을 밟을 때
                        if not sol(2): continue

                    case 'a':
                        if not sol(3): continue

                    case 'F':
                        if not sol(0): continue


    print(ct[out_y][out_x], cat[out_y][out_x])

---

3.  마무리

 

 

참고로 나는 위에 elif에도 뒤에 +1을 붙여야 했는데, 안 붙여서 1시간 동안 시간 초과가 나서 헤맸다 ,,ㅜㅜㅜ

그래서 뒤에서는 모든 if, elif, else를 하나의 함수로 만들었고, 이를 flag로 구분했다.