텀 프로젝트 백준 9466번 BFS

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

문제 이번 가을학기에 ‘문제 해결’ 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, …, sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,…, sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

|3|1|3|7|3|4|6| | :- | :- | :- | :- | :- | :- | :- |

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

from collections import deque
loop = int(input())
for i in range(loop):
    num = int(input())
    f_list = list(map(int,input().split()))
    count = num
    for j in range(num):
        queue = deque([j])
        first = f_list[j]-1
        queue.append(first)
        cycle = False
        while not cycle:
            now = f_list[queue[-1]]-1
            if now not in queue:
                queue.append(now)
            else:
                if first == now:
                    cycle=True
                else:
                    count-=1
                    break
    print(count)

….사이클이 발생하는가 여부를 가지고 하나하나 따져보았습니다.

1번은 3번을 가르키고 3번은 자기 자신을 가르키니 사이클이 생기게 되고 첫번째와 마지막(1,3)이 다르니 팀이 구성되지 않는 것으로 보고 빼나가는 식이었습니다. 2번과 5번도 마찬가지였고 3은 자기자신을 가르키니 사이클이 생기게 됩니다.

4,6,7의 경우 서로 사이클이 생기는 경우이니 괜찮은데 문제는 4,6,7을 한번에 구할 수 없고 따로 4번 돌리고 6번 돌리고 7번 돌리는 식이라 시간초과가 나겠다는 생각은 들었는데

뭔가 뾰족한 방법은 떠오르지 않네요 아마 이번 문제는 BFS보다는 그래프문제로 분류를 했어야 할거 같습니다.

NOT_VISITED = 0
CYCLE_IN = -1

def run(x):
    curr = x
    while True:
        state[curr] = x
        curr = arr[curr]
        if state[curr]==x:
            while state[curr] != CYCLE_IN:
                state[curr] = CYCLE_IN
                curr = arr[curr]
            return
        elif state[curr] != 0:
            return
        
loop = int(input())
for i in range(loop):
    global arr
    global state
    num = int(input())
    arr = [0] + list(map(int,input().split()))
    state = [0]*(num+1)
    ans = 0
    for j in range(1,num+1):
        if state[j]==NOT_VISITED:
            run(j)
    cnt = 0
    for j in range(1,num+1):
        if state[j] != CYCLE_IN:
            cnt+=1
    print(cnt)

리스트를 받을때 숫자의 인덱스를 고려해서 1부터 num+1까지 해서 맞췄습니다. 인덱스를 0부터 계산할려고하니 함수짤때 머리아파서 못하겠더라고요 핵심적인 부분은 사이클이 일어나는 곳을 관리하는 것입니다.

어차피 모든 노드는 하나의 간선을 주는 형태로가니 싸이클을 이루거나 싸이클로 들어가는 형태입니다. 그러면 싸이클을 유지한다면 state를 -1로 만들고 그 이외의 경우에는 다른수가 들어가게 되는데 자신이 싸이클이 아닌 노드를 선택하거나 자신은 싸이클을 이루지 않은 상태인데 싸이클인 노드를 선택하면 팀을 이룰 수 없다는 이야기입니다.

첫번째 예시인 3 1 3 7 3 4 6 을가지고 설명을 하면

현재 curr은 1이 들어오게 됩니다. 그러면 state는 방문을 했으니 state[1]값도 1로 바꿔주고

curr은 친구 1이 가르키는 3으로 경신을 합시다. 아직 state[3]에는 아무숫자도 없으고 0이니 넘어가겠습니다.

curr은 2가 들어오게 됩니다. state[2]를 2로 바꿔줍니다. 그리고 친구 2가 가르키는 curr을 1로 갱신을 합니다.

아직 state[1]는 3을가르키기 때문에 마찬가지로 넘어가게 됩니다.

curr이 3이 되었습니다. state[3]은 3을 담게 됩니다. 그리고 arr[3]역시 3을 가르킵니다.

state[3] == 3을 만족하게 되었습니다. 그리고 state[3]은 사이클안에 들어 있지 않다고 합니다. state[3]을 -1 CYCLE_IN으로 값을 변경해줍니다. 그 다음으로 arr[3]을 보아도 여전히 3입니다. 이제 빠져나옵시다.