[Python 3] BOJ 30627 삼월 초하루

저번 2023 SPC에서 나왔던 문제인데, 당시에는 마땅한 풀이법을 찾지 못했었다.

이후 한 해가 지나고 다시 문제를 풀어보았다.

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

우선적으로, BFS를 이용한 완전탐색을 이용하여 풀이하였다.

먼저 문제 상황을 어떻게 정의할 지 많은 고민을 하였는데,

리스트를 이용하여

[1번 물의 위치, 1번 물의 온도], [2번 물의 위치, 2번 물의 온도],[진행 로그]]

와 같은 방식으로 저장하였다. 즉, 시작할 때 1번, 2번 숙우에 온도 100인 물이 있으므로,

[[1,100],[2,100],[]]

처럼 초기에 정의할 수 있는 것이다.

처음에 풀 때는, 단순히 빈 숙우로 물을 옮기면 된다고 생각하였다.
그러므로 물이 들어있는 숙우에서 물이 없는 숙우로 옮기고, 반복적인 BFS를 실시하였다.
그러나, 이렇게 되면 이론상 2의 40제곱개의 연산까지도 해야할 수 있기에, TLE를 받았다.

시간 초과 풀이

from collections import deque
from itertools import permutations
from copy import deepcopy
n=int(input())
temperature=list(map(int,input().split()))
solution=list(map(int,input().split()))
answer=[[solution.index(1)+1,temperature[0]],[solution.index(2)+1,temperature[1]]]
q=deque()
q.append([[1,100],[2,100],[]])
while q:
    temp=q.popleft()
    if answer==temp[:2]:
        print(len(temp[2]))
        for i in temp[2]:
            print(*i)
        exit(0)
    if temp[0][1]<answer[0][1] or temp[1][1]<answer[1][1]:
        continue
    possible=[1,2,3]
    for i in possible:
        if temp[0][0]==i or temp[1][0]==i:
            continue
        for j in range(1,4):
            if j==temp[0][0]:
                q.append([[i,temp[0][1]-5],temp[1],temp[2]+[[j,i]]])
            elif j==temp[1][0]:
                q.append([temp[0],[i,temp[1][1]-5],temp[2]+[[j,i]]])

print(-1)

앞선 풀이와는 다르게,
log라는 bfs의 visited 리스트를 만들어서,

• 이미 방문한 숙우의 물들의 온도와 위치* 가 이미 있었는지 없었는지 확인하였다.
  이를 통해 시간 초과를 면할 수 있었다.

AC를 받은 풀이

from collections import deque
from itertools import permutations
from copy import deepcopy
n=int(input())
temperature=list(map(int,input().split()))
solution=list(map(int,input().split()))
answer=[[solution.index(1)+1,temperature[0]],[solution.index(2)+1,temperature[1]]]
log=[[[] for _ in range(101)] for _ in range(101)]
q=deque()
q.append([[1,100],[2,100],[]])
log[100][100].append([1,2])
while q:
    temp=q.popleft()
    if answer==temp[:2]:
        print(len(temp[2]))
        for i in temp[2]:
            print(*i)
        exit(0)
    if temp[0][1]<answer[0][1] or temp[1][1]<answer[1][1]:
        continue
    possible=[1,2,3]
    for i in possible:
        if temp[0][0]==i or temp[1][0]==i:
            continue
        for j in range(1,4):
            if j==temp[0][0] and [i,temp[1][0]] not in log[temp[0][1]-5][temp[1][1]]:
                log[temp[0][1]-5][temp[1][1]].append([i,temp[1][0]])
                q.append([[i,temp[0][1]-5],temp[1],temp[2]+[[j,i]]])
            elif j==temp[1][0] and [temp[0][0],i] not in  log[temp[0][1]][temp[1][1]-5]:
                log[temp[0][1]][temp[1][1]-5].append([temp[0][0],i])
                q.append([temp[0],[i,temp[1][1]-5],temp[2]+[[j,i]]])

print(-1)