[백준 12893번] 파이썬 - 적의 적

백준 12893 - 적의 적

시간 제한 2초, 메모리 제한 512MB

# 조건

• 적의 적은 친구 이론이란, A와 적대 관계인 B가 있고, B와 적대 관계인 C가 있을 때 A와 C는 우호 관계에 있다는 이론을 말한다.
• 하지만 이 이론에는 치명적인 단점이 있다.
  • 바로 C와 적대 관계인 D가 있다면, A 역시 D와 적대관계가 되는 것이다.
  • 하지만 또 생각해보면 D와 적대관계인 E가 있다면 E는 A, C와 우호 관계가 된다.
  • 같은 맥락으로, B와 D 역시 우호 관계가 된다.
• 이 이론에 따라 친구를 사귀게 되면 적도 늘어나겠지만 어쨌거나 용재는 친구가 절실하다.
• 하지만 아직 이 이론은 전 우주상에서 엄밀히 증명된 적이 없다.
• 따라서 용재는 이론을 적용하기 전에 먼저 자신의 주위 N명에 관해서 이 이론이 성립하는지를 먼저 검증하고 싶다.
• 용재를 도와 이 이론이 성립할 수 있는지를 알아보자.

입력

• 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다.
• 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다.

출력

• 이론이 성립할 수 있다면 1, 그렇지 않다면 0을 출력하라.

# 접근 방법

• 이분 그래프, 그래프 탐색, 유니온 파인드 등 다양한 방법으로 풀 수 있는 문제이다.
• 나는 단순한 bfs를 이용하여 풀어주었다.
  • 우선 입력받는 적의 관계를 양방향 그래프로 기록해주고 visted를 친구의 수 만큼 설정해준다.
• 1부터 순회하면서 방문한 적이 없다면 deque에 삽입해주고 bfs를 실행해준다.
  • 현재 친구의 번호에서 연결된 노드들을 탐색하며 방문한 적이 없다면 visited[x] * -1을 해준다.
  • 적의 적이라면 양수가 되어 친구가 되고, 아니라면 음수가 되어 적이 된다.
  • 방문한 적이 있는데 이 때 visited[j] == visited[x]라면 즉, 연결되어 있는 노드가 나와 아군이라면 그 관계는 옳지 못하므로 종료해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

N, M = map(int, input().split())  
graph = [[] for _ in range(N+1)]  
visited = [0] * (N+1)  

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

for i in range(1, N+1):  
    if not visited[i]:  
        q = deque()  
        q.append(i)  
        visited[i] = 1  
        while q:  
            x = q.popleft()  
            for j in graph[x]:  
                if not visited[j]:  
                    visited[j] = visited[x] * (-1)  
                    q.append(j)  
                elif visited[j] == visited[x]:  
                    print(0)  
                    exit(0)  
print(1)