[백준] 1707번 이분 그래프(python)

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

1707번: 이분 그래프

 

1. 난이도 레벨4

 

2. 내가 작성한 코드

1. part 라는 list를 이용해 현재 노드와 이어진 노드가 각각 다른 집합을 가지고 있게 나눈다.

 

2. 현재 노드와 이어진 노드가 같은 집합일 경우 모순이 발생한 상황. 따라서 break 한 후 no를 출력한다.

 

from collections import deque
import sys

input = sys.stdin.readline

t = int(input().rstrip())

def bfs(v):
    queue = deque()
    queue.append(v)

    while queue:
        popX = queue.popleft()
        for i in maps[popX]:
            if part[i] == 0 and part[popX] == "A": #칠해져 있지 않고 현재 A인 경우
                part[i] = "B"
                queue.append(i)
            elif part[i] == 0 and part[popX] == "B": #칠해져 있지 않고 현재 B인 경우
                part[i] = "A"
                queue.append(i)
            elif part[i] != 0 and part[i] == part[popX]: #현재 노드와 이어진 노드의 집합이 같은 경우
                return False
    return True

for _ in range(t): #테스트케이스
    v, e = map(int, input().rstrip().split()) #정점/간선
    maps = [[] for _ in range(v+1)]
    part = [0] * (v+1)

    for _ in range(e): #그래프 관계 나타내기
        u, v = map(int, input().rstrip().split())
        maps[u].append(v)
        maps[v].append(u)

    for i in range(1, v+1):
        if part[i] == 0:
            part[i] = "A"
            check = bfs(i)
            if not check:
                break

    if check:
        print("YES")
    else:
        print("NO")

 

나는 A와 B를 이용해서 나눠줬기 때문에 bfs 함수 내에서 확인을 한 번 더 거쳐야 했다.

 

part list를 숫자로 초기화 시키고,

 

1. 방문한 적 없는 경우

 

part[다음노드] = (part[현재노드] + 1) %  2 

 

or part[다음노드] = - part[현재노드]

 

2. 방문한 적 있는 경우

 

part[다음노드] 와 part[현재노드]가 같으면 return False

 

위와 같이 숫자를 이용한다면 더 쉽게 문제를 해결할 수 있다.