[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(2)

문제 출처 : https://www.acmicpc.net/problem/19940

19940번: 피자 오븐

피자 오븐 문제를 수학적으로 푸는 방법을 이전 포스팅을 통해 알아보았습니다.

https://davincicoding.tistory.com/103

[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(1)

수학적으로 어떤 버튼을 누르는 것이 효율적인지 바로 알 수 있다면 문제 없지만 마음이 급하다보면 쉽게 45분이나 55분 버튼을 어떻게 누르는지 생각이 나지 않아 계속 문제 해결이 안될 수 있습니다.

BFS로 풀어보기

이런 경우 BFS로 문제를 해결할 수 있습니다. DFS가 아닌 BFS로 해결하는 이유는 BFS의 특성 때문 입니다. 문제를 읽어보면 아래와 같은 문구가 있습니다.

• 작업 횟수가 동일한 방법이 여러가지가 있을 때, ADDH를 누르는 횟수가 적은것이 사전 순으로 앞서는 것이고, ADDH를 누르는 횟수가 동일하면, ADDT를 누르는 횟수가 적은것이 먼저이다. ADDT를 누르는 횟수가 동일하면 MINT를 누르는 횟수가 적은것이, MINT를 누르는 횟수가 동일하면 ADDO를 누르는 횟수가 적은것이, ADDO를 누르는 횟수가 동일하면 MINO를 누르는 횟수가 적은것이 사전 순으로 앞서는 것이다

이 문제에서는 위와 같이 addh, addt, mint, addo, mino 순서대로 작은 값이 출력되길 원합니다. 이 요구사항을 코드안에 넣을수도 있지만 너무 복잡해지기 때문에 BFS의 특성을 사용하려는 것입니다. BFS는 노드 사이의 거리가 모두 같을 때 최소 거리를 알 수 있습니다.

 

35분의 버튼을 누른 횟수를 생각하면 0, 3, 0, 5, 0으로 누르면 8번만에 35분을 누를 수 있습니다. 또 1, 0, 2, 0 ,5 역시 8번만에 35분을 누를 수 있습니다. 하지만 이 문제에서는 앞의 경우인 0, 3, 0, 5, 0이 답이 됩니다. 왜냐하면 같은 8번이지만 ADDH 버튼을 적게 누른 것이 답이기 때문 입니다.

따라서 BFS를 수행하되 mino, addo, mint, addt, addh 순으로 진행한다고 생각하면 같은 횟수로 버튼을 누른다고 하더라도 addh, addt, mint, addo, mino 순서대로 제일 적은 횟수가 출력되게 됩니다.

코드 작성

그럼 코드를 작성해 보겠습니다

입력 받기

T = int(input())

bfs()
for _ in range(T):
    n = int(input())
    hour = n // 60
    minute = n % 60
    print(time[minute][0] + hour, *time[minute][1:5])

먼저 테스트 케이스 T를 입력 받습니다. bfs 함수 실행 후 T번의 설정한 시간 n을 입력 받습니다. bfs 함수를 실행하면 0분에서 60분까지 최적의 결과를 time이라는 리스트에 들어가게 됩니다. 시간을 늘려주는 addh버튼은 무조건 누르는 것이 좋기 때문에 60으로 나눈 값을 더해주고, 분은 계산된 결과를 출력해 줍니다.

bfs 함수

from collections import deque 
MAX = 61
time = [[0] * 6 for _ in range(MAX)]

def bfs():
    q = deque()
    q.append([0, 0, 0, 0, 0, 0])
    visited = [False] * MAX    
    while q:
        info = q.popleft()
        ah, at, mt, ao, mo, tm = info
        if 0 <= tm <= 60:
            if not visited[tm]:
                visited[tm] = True
                time[tm] = info
                
                q.append([ah, at, mt, ao, mo + 1, tm - 1])
                q.append([ah, at, mt, ao + 1, mo, tm + 1])
                q.append([ah, at, mt + 1, ao, mo, tm - 10])
                q.append([ah, at + 1, mt, ao, mo, tm + 10])
                q.append([ah + 1, at, mt, ao, mo, tm + 60])

bfs 함수 입니다. deque를 사용한 이유는 bfs 함수에서 사용하는 queue를 순차적으로 가져오게 하기 위해서 입니다. 이 문제에서 순서가 중요하기 때문에 순서를 맞춰주기 위해 사용 하였습니다.

0분부터 60분까지 가장 먼저 도착하는 값을 time이라는 리스트에 기억 합니다. q에 append 해주는 순서가 바뀌면 답도 틀려집니다. 따라서 순서를 맞춰주는 것이 중요합니다.

전체 코드

전체 코드 입니다.

from collections import deque 
T = int(input())
MAX = 61
time = [[0] * 6 for _ in range(MAX)]

def bfs():
    q = deque()
    q.append([0, 0, 0, 0, 0, 0])
    visited = [False] * MAX    
    while q:
        info = q.popleft()
        ah, at, mt, ao, mo, tm = info
        if 0 <= tm <= 60:
            if not visited[tm]:
                visited[tm] = True
                time[tm] = info
                
                q.append([ah, at, mt, ao, mo + 1, tm - 1])
                q.append([ah, at, mt, ao + 1, mo, tm + 1])
                q.append([ah, at, mt + 1, ao, mo, tm - 10])
                q.append([ah, at + 1, mt, ao, mo, tm + 10])
                q.append([ah + 1, at, mt, ao, mo, tm + 60])

bfs()
for _ in range(T):
    n = int(input())
    hour = n // 60
    minute = n % 60
    print(time[minute][0] + hour, *time[minute][1:5])