9466번 - 텀 프로젝트(python3)

문제 링크: www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

조별과제를 위해 팀원을 구해야 합니다. 강제로 구성된 팀에 들어가기 싫으면 마음이 맞는 사람과 팀을 짜야겠죠? 그런데 모든 팀원이 서로 마음에 들어하는 것은 힘드니까 팀 구성 요건을 조금 완화했습니다. 모든 사람은 같이 팀플하고 싶은 한 사람을 고를 수 있습니다.

 

예를 들어 A가 B를 선택하고, C는 D를, D는 F를 선택하고, F가 A를 선택하면 A->B->C->D->E->F->A와 같은 cycle이 형성됩니다. 이렇게 cycle을 형성하는 사람들끼리 팀을 짤 수 있게 됩니다. 만약 예시에서 F가 C를 선택하면 C->D->E->F->C와 같은 cycle이 만들어지게 되고, A와 B는 팀을 구하지 못하게 됩니다. 문제에서는 팀을 구하지 못한 사람 수를 출력하면 됩니다. 첫 번째 예시에서는 0을, 두 번째 예시에서는 2를 출력하면 됩니다.

 

다음은 문제 풀이에 사용한 코드입니다.

여기서, 모든 사람은 한 번의 방문만으로 팀에 들어갈 수 있는지 없는지를 판단할 수 있다는 것이 중요합니다. 위 예시에서 C~F까지 팀이 구성되고 나면, A와 B는 어떤 수를 쓰더라도 팀에 들어갈 수 없습니다. 만약 G라는 사람이 A를 선택했다면, 더 이상 탐색할 필요 없이 G는 팀 구성에 실패했다는 것을 알 수 있습니다. 

 

visited는 i번째 사람이 탐색 되었는지를 판단하는 list입니다. 사람의 번호는 1번부터 주어지기 때문에 편의상 m명+1 크기의 list를 사용했습니다. 마찬가지로 choose는 i번째 사람이 누구를 선택했는지를 저장하는 list인데, 이 또한 m명+1 크기로 구성했습니다. safe는 팀을 구성한 사람들을 저장하기 위한 list입니다.

 

visited[i] = False면 아직 i번째 사람을 탐색하지 않았기 때문에 i번째 사람부터 탐색을 시작합니다. 한 번 탐색한 사람은 다시 탐색할 필요가 없다는 사실을 기억해둡시다. 현재 탐색에서 발견한 i번째 사람을 저장하기 위해 team이라는 list를 사용합니다. 또한 탐색했다는 것을 저장하기 위해 visited[i]를 True로 바꿔줍니다. 지금부터는 선택한 사람(nxt)을 따라 꼬리물기를 해야하기 때문에 편의상 cur라는 변수로 현재 보고 있는 사람의 번호를 저장합니다. nxt는 현재 보고 있는 cur번째 사람이 선택한 사람입니다. 여기서 총 3가지 경우가 발생합니다.

 

1. nxt번째 사람을 아직 탐색하지 않았다(visited[nxt] = False)
  - 꼬리물기를 계속합니다. nxt를 team에 저장하고, cur을 nxt로 업데이트 시켜 탐색을 계속합니다.
  - nxt가 탐색되었으니 visited[nxt]를 True로 업데이트합니다.

2. nxt번째 사람이 이미 탐색되었다(visited[nxt] = True)
  - 여기서는 2가지 경우가 발생할 수 있습니다.
  2-1. 이번 cycle에서 nxt를 탐색했다(nxt가 team 내에 존재한다)
    - nxt부터 cycle이 시작되기 때문에 team 내 nxt와 그 이후에 탐색한 사람들을 모두 safe에 저장합니다.
      - A->B->C->D->E->F->C 예시에서는 cur=F, nxt=C일 때 탐색을 종료하고, C,D,E,F를 safe에 저장합니다.
      - A와 B는 앞으로도 탐색할 필요가 없고, 무조건 팀을 구성하지 못합니다.
  2-2. nxt가 이전에 이미 탐색되었다.
      - A->B->C->D->E->F->C 탐색을 마치고 G(cur)가 A(nxt)를 선택한 상황입니다.
      - 더 이상 탐색할 필요가 없고, G는 무조건 팀을 구성하지 못합니다.

1번의 경우는 while문을 계속 반복하면서 탐색을 진행하고, 2-1의 경우는 팀 구성이 가능한 사람들만 safe에 저장하고 while문을 끝냅니다. 2-2의 경우는 현재 team에 들어있는 사람들이 모두 팀을 구성하지 못하므로 아무 것도 하지 않고 while문을 끝냅니다. while문 반복 여부와 상관 없이 탐색된 사람들은 모두 탐색된 시점에서 visited 내 True값을 가지므로(line 18) 더 이상 아무것도 하지 않아도 됩니다.

 

Line 12의 for문이 끝났다면 모든 사람에 대해 탐색이 끝났으므로, 팀을 구하지 못한 사람을 출력하면 됩니다. len(safe)가 팀을 구성한 인원 수니까 m-len(safe)를 출력하면 됩니다.

 

처음에는 cycle을 어떻게 판단해야 하는지 몰라서 고생했는데, 한 번 탐색한 사람은 다시 탐색하지 않아도 된다는 것을 깨닫고 나서 빠르게 문제를 풀었습니다. 저는 while문으로 풀었는데, 재귀로도 풀 수 있습니다.