https://www.acmicpc.net/problem/2207
| 시간 제한 | 메모리 제한 |
| 2초 | 128MB |
문제
국제 가위바위보 협회의 회원인 얼드학원의 원장선생님은 가위바위보를 매우 좋아한다. 종종 학생들이 학원에서 딴짓을 하다 걸렸을 경우, 가위바위보 게임을 해서 처벌 여부를 결정하고는 한다.
어느 날 학원에서 N(1 ≤ N ≤ 10,000)명의 학생들이 딴짓을 하다 걸리게 되었다. 걸린 학생의 수가 너무 많아서, 원장선생님은 새로운 방법을 제안했다. 원장선생님이 총 M(1 ≤ M ≤ 10,000)번 가위바위보를 혼자서 하고, 이때 학생들이 원장선생님이 몇 번째에 무엇을 낼지를 알아맞히면 살려주기로 한 것이다.
그런데 찍기에 소질이 있는 얼드학원의 학생들은 모두 원장선생님의 패턴을 파악하여 살게 되었다. 그래서 원장선생님은 학생들에게 한계를 두기로 했다. 즉, 각각의 학생들은 원장선생님이 몇 번째에 무엇을 낼지 선택할 수 있는데, 이러한 선택을 두 종류만 할 수 있도록 제한을 하였다. 즉, 각각의 학생들은 “원장선생님은 세 번째에서는 가위를 내고, 네 번째에서는 바위를 내실 거죠?” 나, “원장선생님은 첫 번째에서는 바위를 내고, 두 번째에서도 바위를 내실 거죠?” 하는 선택을 할 수 있다. 그 대신 둘 다 맞힐 필요는 없고, 둘 중에 하나라도 맞으면 그 학생은 살 수 있다.
그런데 학생들은 원장선생님의 패턴을 파악하여, 원장선생님이 그날의 기분에 따라 보를 내지 않을 거라는 사실을 알게 되었다.
학생들의 선택이 주어졌을 때, 모든 학생들이 살 수 있는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각각의 학생들의 선택을 나타내는 두 정수 x, y(1 ≤ |x|, |y| ≤ M)이 주어진다. x가 양수일 경우에는 원장선생님이 x번째에 가위를 낼 거라는 의미이며, 음수일 경우에는 원장선생님이 |x|번째에 바위를 낼 거라는 의미이다. y에 대한 입력도 마찬가지이다.
출력
첫째 줄에 답을 출력한다. 모든 학생들이 살 수 있을 때에는 “^_^”을 출력하고, 살 수 없을 때에는 "OTL"을 출력한다.
풀이
문제 설명이 좀 복잡하게 되어있습니다. 원장선생님은 가위 아니면 바위만 낸다고 합니다. 그러면 학생들은 원장선생님의 선택에 따라 바위 아니면 보만 내면 됩니다. 학생들은 두 번의 가위바위보에서 한 번만 이기면 됩니다. 모든 학생들이 두 번의 가위바위보를 언제 할 것인지, 무엇을 낼 것인지 선택했을 때 원장선생님에게 모두가 이길 수 있는 경우가 있다면 "^_^", 없다면 "OTL"을 출력합니다. 예를 들어 누군가 3번째 가위바위보에 "원장선생님은 가위를 낼 거야"라고 추측했는데 또다른 사람이 3번째 가위바위보에 "원장선생님은 바위를 낼 거야"라고 추측하면 이 경우 3번째 가위바위보에서 모두가 이기는 방법은 없습니다. 원장선생님이 무엇을 내든 둘 중 한 명은 반드시 지게 되니까요. 그리고 두 번의 가위바위보 중에서 한 번만 이겨도 된답니다. 각각의 가위바위보의 승패를 논리값으로 표현한다면 (A∨B)가 됩니다. 각 학생들마다 두 변수의 논리합이 절(Clause)로 표현되고, 모든 학생의 절이 True가 되어야 전체 결과가 "^_^"가 될 수 있으므로 이건 2-SAT 문제입니다.
5번의 가위바위보를 한다고 해봅시다. 학생은 6명입니다. 각각의 학생이 이런 추측을 했습니다.
첫 번째 학생: 3 -4
두 번째 학생: -2 4
세 번째 학생: -1 -4
네 번째 학생: -3 5
다섯 번째 학생: 2 -5
여섯 번째 학생: 4 5
첫 번째 학생이 가위바위보에서 한 번 이상 승리하려면 원장선생님이 세 번째에 가위를 내거나 네 번째에 바위를 내야 합니다. 모든 학생의 추측이 최소 하나는 맞아야 하므로 각각을 논리합으로 표현해 논리곱해보면 다음과 같은 식으로 정리할 수 있습니다. (숫자에 대한 논리연산이 아닙니다.)
X = (3∨-4)∧(-2∨4)∧(-1∨-4)∧(-3∨5)∧(2∨-5)∧(4∨5)
첫 번째 절에서 3번째 가위바위보가 -3이라면 반드시 4번째 가위바위보가 -4여야 합니다(-3→-4). 반대로 4번째 가위바위보가 4라면 3번째 가위바위보가 반드시 3이어야 합니다(4→3). 각각의 논리 상태를 정점으로 표현했을 때 모든 절에서 이렇게 2개의 간선이 만들어집니다. 모든 간선을 그래프로 표현하면 아래 그림과 같습니다.
여기서 강한연결요소를 찾아 표시해보면 이렇게 됩니다.
알아보기 쉽게 정리해보면 이렇게 됩니다.
각각의 SCC내에 충돌되는 컴포넌트가 없고, A는 C로, D는 B로, B는 A로 이어짐을 알 수 있습니다. 이 중 B에서 A로 가는 방향은 컴포넌트가 모두 충돌되므로 선택할 수 없고, A에서 C로 또는 D에서 B로 이어지는 SCC 연결을 선택하면 모든 가위바위보에서 모든 학생이 최소 1번의 승리를 할 수 있는 상태를 구성할 수 있습니다.
논리 값 그래프를 입력으로 구성하고 SCC를 Tarjan 알고리즘으로 찾아내서 모든 SCC 내에 충돌하는 컴포넌트가 있는지 확인하는 것으로 해 존재 여부를 확인할 수 있습니다. 파이썬 쓰시면 Tarjan 알고리즘 재귀 깊이가 20,000까지 갈 수 있어서 Recursion Error 뜹니다. sys.setrecursionlimit으로 재귀 깊이 제한 풀어줍시다.
정답 코드
import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def solution():
n, m = map(int, input().split())
graph = [[] for _ in range(m * 2 + 1)]
for _ in range(n):
x, y = map(int, input().split())
graph[-x].append(y)
graph[-y].append(x)
dfsn = [0] * (m * 2 + 1)
finished = [0] * (m * 2 + 1)
stack = deque()
def dfs(now, cnt):
dfsn[now] = cnt
stack.append(now)
res = dfsn[now]
for next in graph[now]:
if dfsn[next] == 0:
res = min(res, dfs(next, cnt + 1))
elif finished[next] == 0:
res = min(res, dfsn[next])
if res == dfsn[now]:
scc = set()
while stack:
t = stack.pop()
if -t in scc:
print('OTL')
exit()
else:
scc.add(t)
finished[t] = 1
if t == now: break
return res
for i in range(-m, m + 1):
dfs(i, 1)
print('^_^')
solution()
