BOJ 9466: 텀 프로젝트 [Python 3]

골드 3 난이도의 텀 프로젝트라는 문제를 풀어보았다.

문제를 해석해보자면, 서로서로 프로젝트를 같이 하고 싶은 학생들끼리 그룹을 짜주려고 하는데, 4번이 7번, 7번이 6번 6번이 4번, 즉 서로서로를 꼬리잡기 하듯이 고르면 같은 그룹에 넣어주는 구조이다.

만약 자기 자신을 고르면, 혼자 팀이 된다. (현실 반영...)

내용 자체는 쉽지만 구현하기가 어려웠다.

---

코드이다.

t=int(input())
for _ in range(t):
    n=int(input())
    data=[0]+list(map(int,input().split()))
    visited=[False for _ in range(n+1)]
    res=0
    for i in range(1,n+1):
        if visited[i]:
            continue
        num=i
        q=[num]
        visited[num]=True
        while True:
            newnum=data[q[-1]]
            if visited[newnum]:
                if newnum in q:
                    visited[newnum]=True
                    res+=(len(q)-q.index(newnum))
                break
            else:
                q.append(newnum)
                visited[newnum]=True
    print(n-res)

먼저, t개의 케이스가 있기 때문에 반복문으로 input을 받고, 누가 어떤 사람을 고를지 데이터를 받았다.

이후, DFS알고리즘을 응용해서 문제를 풀었다.

만약 한 사람이 누구를 고르면, 그 고른 사람이 누구를 골랐는지, 이렇게 돌고 돌리다가 만약 앞서 골랐던 사람이 선택을 당하면, 앞서 골랐던 사람 중 선택을 당한 사람부터 마지막 고른 사람까지 같은 그룹이다.

예시로,

1->2,

2->3,

3->4,

4->2를 골랐다고 해보자.

 

추적 과정은 다음과 같다.

1번은 2번을, 2번을 3번을, 3번은 4번을 추적한다.

이후 4번이 2번을 선택하였기에,

2,3,4번은 res에 넣어주고, 이후 번호부터 다시 search 한다.

 

위 코드에서는 앞 사람이 선택할 때마다, q에 넣고, q 안에 있는 아이가 선택당하면, res에 값을 추가한다.

(res는 그룹에 포함된 총 사람이다.)

 

마지막에 총 사람 중 그룹에 포함 된 사람을 구하면, 정답이다.

(n-res)