[백준/3648] 아이돌 (Python)

Problem : https://www.acmicpc.net/problem/3648

3648번: 아이돌

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:25:55

 

---

 

문제 설명

 

 

상근이는 오디션 프로그램 대한민국 아이돌의 예선에 참가중이다.

대한민국 아이돌 오디션 프로그램에서 참가자는 심사위원에게 10분동안 자신의 매력을 발산할 기회를 갖는다. 모든 참가자가 경연이 끝난후에, 심사위원은 모두 모여서 투표를 하게 된다. 각 심사위원은 다음 라운드에 꼭 진출시켰으면 하는 사람(찬성)이나 이번 라운드에서 꼭 탈락시켰으면 하는 사람(반대)을 두 명 고른다. 한 심사위원이 찬성표를 두 개 내는 것과 반대표를 두 개 내는 것도 가능하며, 찬성과 반대를 각각 하나씩 내는 것도 가능하다. 또, 반드시 두 표를 내야 한다.

다음 라운드에 진출하는 참가자의 수는 정해져 있지 않다. 즉, 실력이 참가자의 경연이 모두 나쁜 경우에는 다음 라운드에 진출하는 참가자가 없을 수도 있고, 모두 엄청난 경연을 한 경우에는 모든 참가자기 다음 라운드에 진출할 수도 있다.

상근이는 심판들이 자신의 프로그래밍 능력에 큰 관심을 보이지 않을 것 같아 걱정하고 있다. 따라서, 상근이는 해킹을 이용해서 다음 라운드에 진출하려고 한다. 상근이는 투표 집계 시스템을 해킹해서, 다음 라운드 진출자를 선택하는 프로그램을 바꿔치기 하려고 한다. 하지만, 의심을 받지 않아야 한다.

각 심사위원은 자신이 행사한 두 표 중 적어도 하나는 결과에 영향을 미쳐야 한다고 생각을 한다. 두 표 모두와 반대되는 결과가 나오면, 심사위원은 투표 결과에 대해서 의심을 하게 된다. 예를 들어, 고원섭 심사위원이 박현수 참가자에게 찬성을, 김선영 참가자에게 반대를 한 경우를 생각해보자. 이 경우에 김선영이 다음 라운드에 진출하고, 박현수가 탈락을 하게 된다면, 두 결과가 모두 영향을 미치지 못했기 때문에, 고원섭 심사위원은 투표를 의심하게 된다.

상근이는 심사위원의 의심을 받지 않으면서, 다음 라운드에 진출하는 목록을 만들 수 있는지를 알고 싶어 한다. 당연히 이 목록에는 상근이가 포함되어 있어야 한다. 각 심사위원이 투표한 결과가 주어졌을 때, 상근이가 포함된 다음 라운드 진출 목록을 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 참가자의 수 n (2 ≤ n < 1000) 과 심사위원의 수 m (1 ≤ m < 2000)이 주어진다.

다음 m개 줄에는 각 심사위원이 행사한 투표의 정보 a와 b가 주어진다. (1 ≤ |a|, |b| ≤ n, |a| ≠ |b|) 정보가 x < 0인 경우에는 그 심사위원이 참가자 |x|에게 반대표를 행사한 것이고, x > 0인 경우는 |x|에게 찬성을 던진 것이다.

참가자의 번호는 1번부터 n번이다. 상근이는 1번 참가자이다. 

 

출력

 

각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다.

 

입력 예시

 

4 3
1 2
-2 -3
2 4
2 4
1 2
1 -2
-1 2
-1 -2

 

출력 예시

 

yes
no

 

 

---

 

풀이

 

심사위원이 두 표 a, b를 던지고, 둘 중 하나 이상이 반영되어야 하므로 a OR b이다. 또한 모든 심사위원을 만족해야 하므로 이는 2-SAT 문제의 변형이라고 볼 수 있다. 아래 문제와 본질적으로 풀이는 동일하니 한 번 참고해보아도 좋다.

 

 

2023.12.21 - [알고리즘 문제/백준] - [백준/11280/11281] 2-SAT - 3 / 4 (Python)

[백준/11280/11281] 2-SAT - 3 / 4 (Python)

 

 

우리는 여기서 또한, 상근이가 찬성표를 받아 합격할 수 있는가? 라는 조건 역시 충족해야 한다. 이는 상근이의 번호인 a1이 True여야 함을 의미한다. 그런데 여기서

 

a = True

=> a OR a = True

=> ~a -> a = True

 

로 동치임을 알 수 있다. 즉 가상의 "상근이에게 찬성표 두 표를 던진" 심사위원을 하나 더 추가하여 고려하면 된다.

 

 

풀이 코드

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def cvt(x) :
  if x < 0 :
    return -x-1+N
  return x-1
    
def neg(x) :
  return (x + N) % (2*N)

def solve() :
  global N, idx, scc_idx
  lines = input()
  if lines == "" :
    return False
  N, M = map(int, lines.split())
  edge_dict = defaultdict(list)
  edge_dict[N].append(0)
  stk = list()
  idx, scc_idx = 0, 0
  visited = [-1]*(2*N)
  scc_result = [-1]*(2*N)

  for _ in range(M) :
    a, b = map(int, input().split())
    a = cvt(a)
    b = cvt(b)
    edge_dict[neg(a)].append(b)
    edge_dict[neg(b)].append(a)

  def dfs(node) :
    global idx, scc_idx
    visited[node] = result = idx
    idx += 1
    stk.append(node)
    for nxt in edge_dict[node] :
      if scc_result[nxt] > -1 : 
        continue
      if visited[nxt] == -1 :
        dfs(nxt)
      result = min(result, visited[nxt])
    if result == visited[node] :
      while True :
        n = stk.pop()
        scc_result[n] = scc_idx
        if n == node :
          break
      scc_idx += 1
    visited[node] = result

  for i in range(2*N) :
    if scc_result[i] == -1 :
      dfs(i)

  for i in range(N) :
    if scc_result[i] == scc_result[neg(i)] :
      print("no")
      return True
  print("yes")
  return True

while True :
  if not solve() :
    break

풀이 완료!