[백준 파이썬] 1953 팀배분

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

1953번: 팀배분

 

문제

각 학생별로 싫어하는 학생의 번호가 주어지고 각 학생이 싫어하는 학생과 다른 팀이 되도록 분배하는 문제이다

 

---

풀이

해당 문제를 풀기위해 DFS를 사용하였다.

1. DFS

DFS란 깊이 우선 탐색으로 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

 

만약 1번학생이 싫어하는 학생에 3번일 경우 3번을 1번학생과 다른팀에 배정 후 3번학생이 싫어하는 학생을 찾는 방식으로 DFS를 사용하였다.

def DFS(human, isBlue):
    if (isBlue):
        blue.append(human)
    else:
        white.append(human)
    for i in ban[human]:
        if i in queue:
            queue.remove(i)
            DFS(i, not isBlue)

해당 코드처럼 사람번호와 해당사람의 팀을 넣어주고 넣어준 사람이 싫어하는 사람을 탐색해서 팀을 배분하는 방식을 사용했다. 

하지만 이방법의 경우 처음 넣어준 사람과 모든사람이 어떤식으로든 연결되어 있지 않은경우 모든 경우의 수를 탐색할 수 없기 때문에 deque를 사용하였다.

while queue:
    human = queue.popleft()
    DFS(human, True)

시작 시 deque에 사람의 번호를 모두 넣어준 후 배정된 사람은 지워 모든 사람이 배정될때까지 반복하게 하였다.

 

 

---

코드

from collections import deque

n = int(input())
queue = deque()
blue = []
white = []

ban = [[]]
for i in range(n):
    ban.append(list(map(int, input().split()))[1:])
    queue.append(i+1)


def DFS(human, isBlue):
    if (isBlue):
        blue.append(human)
    else:
        white.append(human)
    for i in ban[human]:
        if i in queue:
            queue.remove(i)
            DFS(i, not isBlue)


while queue:
    human = queue.popleft()
    DFS(human, True)

blue.sort()
white.sort()
print(len(blue))
for i in blue:
    print(i, end=" ")
print()
print(len(white))
for i in white:
    print(i, end=" ")