[ 백준 / G4 / 파이썬 Python ] 팀배분

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

1953번: 팀배분

 

코드

---

def dfs(idx, t):
    result[idx],visit[idx] = t,1
    for i in [x for x in range(n) if hater[idx][x] == 1 and visit[x] == 0]:
        dfs(i, -t)

n = int(input())
hater = [[0] * n for i in range(n)]
for i in range(n):
    m,*arr = list(map(int, input().split()))
    for j in arr:
        hater[i][j - 1] = 1
        hater[j - 1][i] = 1

visit = [0 for i in range(n)]
result = [0 for i in range(n)]

for i in range(n):
    if visit[i] == 0:
        dfs(i, 1)

print(result.count(1))
for x in [i+1 for i in range(n) if result[i] == 1]: print(x, end=" ")
print()
print(result.count(-1))
for x in [i+1 for i in range(n) if result[i] == -1]: print(x, end=" ")

 

풀이

---

이 문제가 어려운 이유는 한 학생이 싫어하는 학생의 싫어하는 학생... 이런 관계를 생각해내기 어렵기 때문이다....어렵다 나도..

먼저 a학생이 b학생을 싫어하면 b학생도 a학생을 싫어하므로 양방향으로 매핑시켜준다.

for i in range(n):
    m,*arr = list(map(int, input().split()))
    for j in arr:
        hater[i][j - 1] = 1
        hater[j - 1][i] = 1

 

한 학생씩 팀을 찾아주는데 청팀과 백팀 두 팀으로 나뉘므로 1과 -1로 간단하게 표시해준다.

또한 한 탐색에서 최대한 많은 학생들의 팀을 찾아준다. 예를 들어, 1번 학생이 2,3,4번 학생을 싫어하면 1번 학생의 반대편 방향에 2,3,4 학생을 넣어준다.

위에서 말한 이 문제가 어려운 점을 해결하기 위해 재귀적 함수 호출방법인 DFS를 사용했다.

싫어하는 사람이 싫어하는 사람은 반대편으로 넣어주기 위해 탐색의 깊이를 나아갈 때마다 팀상태를 1,-1,1,-1과 같이 변경해준다.

def dfs(idx, t):
    result[idx],visit[idx] = t,1
    for i in [x for x in range(n) if hater[idx][x] == 1 and visit[x] == 0]:
        dfs(i, -t)

이렇게 하면 1과 -1로 간단하게 팀을 나눌 수 있다.