https://jungol.co.kr/problem/2387
| 시간 제한 | 메모리 제한 |
| 초 | MB |
문제
당신은 숲속에서 당신의 간식을 빼앗아간 원숭이 로봇을 쫓고 있다.
원숭이 로봇은 워낙 기민하게 움직이지만, 당신은 세계에서 가장 좋은 머신건을 이용하여 원숭이 로봇을 잡을 수 있다.
원숭이 로봇은 잡히지 않기 위해 어떤 나무 뒤에 숨는다.
당신은 이러한 사실을 알고 있고 따라서 특정 나무를 골라서 그곳에 사격을 한다.
당연히 세계에서 가장 좋은 총이기 때문에 나무는 쉽사리 뚫리게 되며, 만약 원숭이 로봇이 그 나무 뒤에 숨어 있을 경우 원숭이 로봇은 총을 맞아 작동이 멈추게 된다.
만약 원숭이 로봇이 사격한 나무에 없을 경우 원숭이 로봇은 사격 소리를 듣고 조용히 이웃의 나무(한 번에 바로 이동할 수 있는 나무)로 이동하게 된다.
워낙 기민한 원숭이 로봇이기 때문에 당신이 알아채지 못하게 이동을 한다.
원숭이 로봇이 한 나무에 계속 숨지 않으며, 반드시 사격 후에 살아있을 경우에는 원숭이 로봇은 이웃한 나무로 이동하게 된다.
실탄이 별로 없기 때문에 모든 가능한 경우에 대해 사격 횟수를 최소화하여 원숭이 로봇을 잡고자한다.
위의 그림에서 왼쪽 그림의 경우에는 둘 중에 한곳을 계속 사격하게 될 경우에 원숭이 로봇을 잡을 수 있다. 만약 원숭이 로봇이 처음에 그 나무에 없을 경우에는 다음 사격에서 작동이 멈추게 된다.
오른쪽의 그림의 경우에는 원숭이 로봇을 절대로 잡을 수 없는 경우이다.
입력
입력은 여럿의 테스트 케이스(최대 15개)로 이뤄진다. 테스트케이스 사이에는 빈 줄 하나가 입력된다.
테스트 케이스의 첫 번째 줄에는 나무의 개수 $N (1 \leq N \leq 21)$과 이웃한 나무의 쌍 $M (0 \leq M \leq 210)$이 입력된다.
만약 나무의 개수 $N$과 이웃한 나무의 쌍 $M$ 모두 0 이 입력될 경우 이를 처리하지 않고 프로그램을 종료한다.
나무는 $0$번부터 $N-1$번까지 번호가 부여된다.
그 다음 줄부터는 $M$개의 줄에 $0$이상 $N-1$이하의 정수 $a$와 $b (a \neq b )$가 공백을 사이에 두고 입력된다. 이는 $a$번 나무에서 $b$번 나무로, 혹은 $b$번 나무에서 $a$번 나무로 바로 이동이 가능함을 뜻한다. 이때, 임의의 나무에서 임의의 다른 나무까지 가는 방법이 항상 존재한다.
출력
각 테스트 케이스에 대해 최악의 경우에 원숭이 로봇을 잡을 수 없을 경우에는 `Impossible`을 출력하며,
그렇지 않을 경우 다음과 같은 형식으로 출력한다.
$S : T_1 \ T_2 \dots \ T_S $
여기서 $S$는 모든 경우에도 원숭이 로봇을 잡을 수 있게 하기 위한 최소의 사격 수고 $T_i$는 $i$번째에 사격해야 하는 나무의 번호를 뜻한다.
사격하는 순서가 여럿 있을 경우 사전 순으로 가장 빠른 것을 출력한다.
풀이
gpt 5.5 Thinking에게 질문하면서 배운 내용입니다. 나무가 21개라고 하길래 TSP인가? 싶어서 TSP로 푸는 거냐고 물었더니, 미니맥스, DP 문제라고 합니다. 미니맥스가 뭐지?
1. Minimax
미니맥스 알고리즘은 체스, 오목, 틱택토처럼 두 명이 번갈아 두는 게임에서 AI가 “상대도 최선을 다해 둔다”고 가정하고, 내가 얻을 수 있는 최악의 결과를 최대한 좋게 만드는 수를 고르는 방법입니다.
핵심 아이디어는 가능한 수를 트리 탐색처럼 살펴보는 건데요, 예를 들어 내가 둘 차례라면
- 내가 둘 수 있는 모든 수를 찾기
- 각 수에 대해 상대가 둘 수 있는 대응 찾기
- 상대가 최선의 대응을 한다고 가정하기(상대는 내 점수를 최소화하려고 함: mini)
- 그 중에서 내가 얻을 수 있는 최선의 결과를 찾기(나는 내 점수를 최대화 하려고 함: max)
입니다. 그래서 이름도 Minimax라고 합니다.
이 알고리즘은 모든 정보가 공개되고 운의 요소가 없는 1대1 제로섬 게임에서 활용할 수 있습니다. 반대로 상대의 정보를 알 수 없는 카드 게임에서는 사용하기 어렵습니다. 항상 발생할 수 있는 모든 경우의 수를 따져야 하기 때문입니다.
하지만 그럼에도 이 알고리즘은 살펴봐야 할 경우의 수가 너무 많다는 문제가 있습니다. 그래서 다음과 같은 가지치기 방법을 함께 사용합니다.
- depth 제한: 수순을 끝까지 살펴보지 않고 5수, 6수 등 제한을 둡니다.
- 평가 함수: 판세를 보고 점수를 매겨 얼마나 유리한지 판단합니다.
- alpha-beta 가지치기: 결과과 확실히 더 나쁜 선택지 등 계산할 필요가 없는 경우의 수를 잘라냅니다.
실제로 미니맥스 알고리즘을 채택한 경우로 IBM의 딥 블루(Deep Blue)가 있습니다. 1997년 체스 세계 챔피언 카스파로프를 이겼습니다. 전통적 체스 엔진들이 미니맥스 알고리즘을 사용해왔는데, 알파고 등 최근 AI에서는 몬테카를로 트리 탐색(MCTS)과 딥러닝을 결합한 방식을 사용한다고 합니다.
2. 적용
나무가 최대 21개이기 때문에 TSP인가? 라는 생각을 한 이유가 TSP에서 21자리 비트필드를 사용했었던 기억이 남아있어서 였습니다. TSP는 보통 $O(n!)$이기 때문에 탐색 깊이 자체는 12~14정도가 한계였던 기억이 납니다.
하여튼 비트필드라는 힌트를 던져주고 있던 거고요. 그래서 원숭이가 존재할 수 있는 나무를 `1`, 존재할 가능성이 없는 나무를 `0`으로 표시하면 최대 21자리의 비트필드가 됩니다. 이걸로 경우의 수를 관리할 수 있게 됩니다.
나무가 4개 있다고 해봅시다. 초기에는 모든 나무에 원숭이가 존재할 가능성이 있으므로 비트 상태는 `1111`이 됩니다. 이제 나무의 연결 관계를 이렇게 가정해보겠습니다.
그럼 0번 나무에 총을 쏴본다고 가정하면, 0번 나무에 원숭이가 있던 경우는 사라집니다. 이제 `1110`이 되었습니다.
그리고 남은 세 나무에 존재할 수 있는 원숭이들이 연결된 나무로 움직일 수 있게 됩니다.
방금 쏴버린 0번 나무로 1, 2, 3번 나무에 있던(정확히는 가능성이 있는) 원숭이가 올 수 있게 됩니다. 그런데, 2번 나무에 있던 원숭이는 0번으로 밖에 이동할 수 없는데, 0번에 존재할 수 있는 원숭이가 사라졌으므로 2번으로 올 원숭이가 없습니다. 0번 나무에 총을 쏘면 그 다음 상태에서 2번 나무에는 원숭이가 있을 수 없게 됩니다. 이제 `1011`이 됩니다.
x번 나무를 쏴버렸을 때 다음 상태를 결정하는 방법은 이렇습니다. i번째 나무 `tree[i]`에 그 나무와 이어진 나무들을 비트로 표시합니다.
현재 상태 `bit`에 대해, x번째 나무를 쏜다면 x번째 비트를 제외한 모든 비트 `~x`에서 나무의 비트 `tree[~x]`를 or 연산 시키면 됩니다. 아까 0번 나무에 총을 쏜 경우는 `tree[1] | tree[2] | tree[3] = 1001 | 0001 | 0011 = 1011`입니다.
이제 새롭게 만들어진 상태 `1011`이 방문한 적이 있는지 없는지 확인하면 됩니다. 방문한 적이 있다면, 이보다 더 적은 총을 쏘면서 이 상태를 만들 수 있으니 탐색하지 않아도 됩니다. 하지만 방문한 적이 없다면 이전 비트에 도달하기까지의 비용에 1을 더한 값을 방문 비용으로 처리하고, `bfs`에 현 상태를 담아 탐색을 이어갑니다.
문제에서는 쏴야 할 나무의 순서까지 출력하라고 했으니 이전에 어떤 나무를 쐈는지도 따로 기록해둬야 합니다.
정답 코드
상태 `state`에서 `t`번째 나무를 쏠 때 `next state`를 반환하는 함수입니다.
def shot(state, t):
ret = 0
k = 1
for i in range(n):
if i != t and state & k:
ret |= tree[i]
k <<= 1
return ret
