[백준] 1953번 팀배분 (Python)

백준 1953 팀배분

DFS를 활용한 풀이다. 간단한 문제지만 코드를 보다 깔끔하게 짤 수 있는 방법이 없을까 고민했던 문제다. 문제에서 중요한 포인트는 다음과 같다.

1. 만들 수 있는 팀이 2개 밖에 되지 않기 때문에, 한 사람의 팀이 정해졌을 때, 해당 사람에 대해 적대적인 사람은 팀이 고정된다.
2. DFS 탐색을 활용해 임의의 사람을 시작으로 서로 적대적인 사람들을 모두 배분할 수 있다.
3. 단, 그룹이 여러 개로 나뉘어질 수 있기 때문에 DFS 탐색만으로는 모든 사람의 팀을 나눌 수 없다.
4. candidate라는 set의 element가 존재한다면 아직 팀이 정해지지 않은 그룹을 다시 DFS탐색을 통해 팀을 나눈다.

import sys

def DFS(person, is_blueteam):
    if is_blueteam:
        blue_team.append(person)
    else:
        read_team.append(person)
    for hate in ban[person]:
        if hate in candidate:
            candidate.remove(hate)
            DFS(hate, not is_blueteam)

inp = sys.stdin.readline
n = int(inp())
blue_team = []
read_team = []
ban = [[]] + [list(map(int, inp().split()))[1:] for _ in range(n)]
candidate = set(range(1, n + 1))
while candidate:
    c = candidate.pop()
    DFS(c, True)    

blue_team.sort()
read_team.sort()
print(len(blue_team))
print(*blue_team)
print(len(read_team))
print(*read_team)