[Python] 19240번 장난감 동맹군

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

19240번: 장난감 동맹군

---

 

24/03/16

 

 

이분 그래프임을 알아낸다면 쉽게 해결할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

장난감을 그래프의 노드, 동맹이 될 수 없는 장난감의 쌍을 두 노드를 이은 간선이라고 간주한다면, 동맹이 될 수 없는 장난감 쌍 끼리는 서로 다른 동맹군이어야 한다는 조건은 이분 그래프의 조건을 만족한다.

 

따라서 주어진 그래프가 이분 그래프의 조건을 만족함을 알아내기만 하면 충분하다.

 

이는 DFS로 구현해도 되고 BFS로 구현해도 된다.

 

나의 경우 BFS로 구현했다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 19240번 장난감 동맹군
# 너비 우선 탐색, 이분 그래프
'''
접근 방법:
동맹이 될 수 없는 장난감 쌍 = 간선
장난감 = 노드
동맹이 될 수 없는 장난감 쌍 끼리는 서로 다른 동맹군이어야 함
= 이분그래프
'''
import sys
input = sys.stdin.readline
from collections import deque

def solve():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    visited = [0 for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x -= 1; y -= 1;
        graph[x].append(y)
        graph[y].append(x)
    for i in range(N):
        if visited[i] == 0:
            queue = deque()
            queue.append((i, 1))
            visited[i] = 1
            while queue:
                node, color = queue.popleft()
                for near_node in graph[node]:
                    if visited[near_node] == 0:
                        visited[near_node] = color^1^2
                        queue.append((near_node, color^1^2))
    flag = True
    for node in range(N):
        S = set(visited[i] for i in graph[node])
        if visited[node] == 1:
            if 1 in S:
                flag = False
                break
        elif visited[node] == 2:
            if 2 in S:
                flag = False
                break
    print('YES' if flag else 'NO')

T = int(input())
for _ in range(T):
    solve()