[BOJ/Python] 백준 9466 텀 프로젝트

문제

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

풀이

풀이 1

• 78% 시간 초과

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

T = int(input().rstrip())

def dfs(cur, team) :

    for g in graph[cur] :
        if not isTeam[g] :
            if g in team :
                idx = team.index(g)
                for i in range(idx, len(team)): isTeam[team[i]] = 1
                return
            else :
                team.append(g)
                dfs(g, team)

for tc in range(T) :
    n = int(input().rstrip())

    students = list(map(int, input().rstrip().split()))
    students.insert(0, 0) # 1번 idx에 1번 학생이 오도록

    graph = [[] for _ in range(n + 1)]

    for i in range(1, n + 1) : graph[i].append(students[i])
    isTeam = [0 for _ in range(n + 1)]

    for i in range(1, n + 1) :
        if not isTeam[i] :
            team = [i]
            dfs(i, team)

    print(n - sum(isTeam))

풀이 2

• 80% 시간 초과

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

T = int(input().rstrip())

def dfs(cur, team, depth) :

    for g in graph[cur] :
        if not isTeam[g] :
            if str(g) in team :
                idx = team[str(g)]
                for i in team :
                    if team[str(i)] >= idx : isTeam[int(i)] = 1
                return
            else :
                team[str(g)] = depth
                dfs(g, team, depth + 1)

for tc in range(T) :
    n = int(input().rstrip())

    students = list(map(int, input().rstrip().split()))
    students.insert(0, 0) # 1번 idx에 1번 학생이 오도록

    graph = [[] for _ in range(n + 1)]

    for i in range(1, n + 1) : graph[i].append(students[i])
    isTeam = [0 for _ in range(n + 1)]

    for i in range(1, n + 1) :
        if not isTeam[i] :
            team = {str(i) : 0}
            dfs(i, team, 1)

    print(n - sum(isTeam))

풀이2 설명

문제를 읽고 처음 떠올린 풀이 방법은

• 그래프로 입력 받고 dfs로 cycle이 있는지 확인
  • cycle : 이미 visited == 1 인데 또 방문하는 경우
• input이 100,000이므로 O(n^2)가 되지 않도록 주의

따라서

    1. 팀을 이루지 못한 학생에 대해서 (isTeam == 0) dfs를 돌리는데

    2. 다음 학생이 cycle을 이루면(g in Team), 사이클인 부분부터 끝까지 team 만든 것으로 처리 (isTeam = 1)

    3. cycle 이루지 못하면, 일단 team에 추가하고 다음 학생 탐색 진행

    4. 전체 학생에서 팀을 이룬 학생(isTeam == 1) 수를 뺀 것이 정답

과 같이 코드를 작성했다.

78% 에서 시간 초과되었고 혹시 인덱스를 직접 찾는 부분에서 시간이 많이 소요되나 싶어서 dictionary로도 해보았지만, 역시 근본적 해결은 아니었다..

dictionary를 이용하였을 때에는 key에 학생의 번호, value에 몇 번 째 깊이에서 team에 추가되었는지를 담아서

cycle이 있을 때 value로 cycle에 해당하는 학생들을 확인했다.

최종 풀이

• 60908 KB, 2656 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

def dfs(cur) :
    global ans

    visited[cur] = 1
    team.append(cur)
    nxt = students[cur]

    if visited[nxt] :
        if nxt in team :
            ans += team[team.index(nxt) : ]
        return
    else :
        dfs(nxt)

T = int(input().rstrip())

for _ in range(T) :
    n = int(input())
    students = list(map(int, input().rstrip().split()))
    students.insert(0, 0)
    visited = [0 for _ in range(n + 1)]
    ans = []

    for i in range(1, n + 1) :
        if not visited[i] :
            team = []
            dfs(i)

    print(n - len(ans))

최종 풀이 설명

앞선 풀이에서 탐색하였더라도 팀을 이루지 못한 경우에 다시 탐색하여서 중복이 발생하고 있었다.

하지만, 한 번 팀을 이룰 수 없는 것을 확인하면 다시 확인할 필요가 없기 때문에 이 부분이 중복되지 않도록 코드를 다시 작성하였다.

1. 방문하지 않은 경우에 대해서 dfs를 하는데, 

2. dfs 내용은

• 일단 방문 처리
• team으로 추가
• 다음 노드 확인
  • 다음 노드를 방문 한 적 있고 team에 있으면(= cycle), cycle인 부분만 ans에 추가
  • 다음 노드 방문했는데 team에 없으면 의미 없으므로 return
  • 다음 노드 방문 한 적 없으면 계속 dfs 탐색 진행

3. ans에 team을 이룬 학생이 담기므로, 전체 학생에서 ans의 길이를 빼주면 팀을 이루지 못한 학생 수를 구할 수 있다.

배운 점

중복 탐색을 하고 있지는 않은지 잘 확인하기 !