[백준9466/골드3] 텀 프로젝트 - Python

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

 

 

✅ 문제 조건

1. 사이클이 생기는 학생들만 팀 완성

2. 사이클이 생기지 않는 학생은 팀 생성 불가능

 

 

✅ 접근 방법

1. 1번 학생부터 시작해서 n번 학생까지 dfs를 한다 (visited 배열로 방문표시)

2. 탐색 도중 이미 방문한 학생이 있을 경우, 사이클 발생

2-1. 이때 사이클이 발생한 학생을 다시 찾는다

2-2. ex. 1 > 2> 3> 2 로 탐색할 경우, 2번과 3번 학생 사이클 발생, 1번은 팀 이루어지지 못함  (finished 배열로 dfs가 완료되었는지 표시)

 

 

✅ 구현

 

1. 입력 및 결과

n = int(input())
students = list(map(lambda x: int(x) - 1, input().split()))
visited = [False] * n   # 아직 방문하지 않은 노드를 대상으로만 dfs 시작
finished = [False] * n  # 사이클 여부 판단 시, 이미 사이클을 판별한 노드인지 확인할 때 사용
cycle = []              # 팀을 이룬 학생들 번호

for i in range(n):
    if not visited[i]:
        path = []       # dfs 탐색을 하며 연결된 학생들 배열
        dfs(i)

 

 

2. dfs 함수

def dfs(i):
    global cycle
    visited[i] = True
    path.append(i)
    next_student = students[i]     # i 학생이 선호하는 학생 번호

    if not visited[next_student]:  # 다음 학생이 아직 dfs 탐색하지 않은 학생일 경우 dfs 탐색
        dfs(next_student)
    elif not finished[next_student]:              # 다음학생 dfs 탐색 시작했고, 아직 완료되지 않았을 경우
        cycle += path[path.index(next_student):]  # 사이클이 생긴 학생들만 팀을 이룬 학생 배열에 추가

    finished[i] = True  # dfs 완료 표시

 

 

 

✅ 정답 코드

python 62312 KB, 3552 ms

'''
0번 학생부터 순회하며 연결 고리 찾기
'''

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

def dfs(i):
    global cycle
    visited[i] = True
    path.append(i)
    next_student = students[i]     # i 학생이 선호하는 학생 번호

    if not visited[next_student]:  # 다음 학생이 아직 dfs 탐색하지 않은 학생일 경우 dfs 탐색
        dfs(next_student)
    elif not finished[next_student]:              # 다음학생 dfs 탐색 시작했고, 아직 완료되지 않았을 경우
        cycle += path[path.index(next_student):]  # 사이클이 생긴 학생들만 팀을 이룬 학생 배열에 추가

    finished[i] = True  # dfs 완료 표시

for _ in range(int(input())):
    n = int(input())
    students = list(map(lambda x: int(x) - 1, input().split()))
    visited = [False] * n   # 아직 방문하지 않은 노드를 대상으로만 dfs 시작
    finished = [False] * n  # 사이클 여부 판단 시, 이미 사이클을 판별한 노드인지 확인할 때 사용
    cycle = []              # 팀을 이룬 학생들 번호

    for i in range(n):
        if not visited[i]:
            path = []   # dfs 탐색을 하며 연결된 학생들 배열
            dfs(i)

    print(n - len(cycle))

 

 

 

❗️ 실패 코드

메모리 초과 : dfs 탐색 순서 배열을 전역으로 관리하지 않고 재귀 깊이만큼 새로운 리스트 객체를 계속 생성하여 메모리 낭비

'''
0번 학생부터 순회하며 연결 고리 찾기
'''

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

for _ in range(int(input())):
    n = int(input())
    students = list(map(lambda x: int(x)-1, input().split()))
    visited = [False] * n
    used = [False] * n

    def dfs(i, arr):

        if not visited[students[i]]:
            visited[students[i]] = True
            dfs(students[i], arr + [students[i]])  # 새로운 리스트 생성

        else:
            if students[i] in arr:
                made = False
                used[students[i]] = True
                for idx, student in enumerate(arr):
                    if student == students[i]:
                        made = True
                    if made:
                        used[student] = True
            return

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

    print(used.count(False))

 

 

 

💡 정답 코드 리팩토링

매번 사이클이 발생할 때 마다 슬라이싱해서 학생을 추가해줬는데 굳이 배열을 만들어서 추가할 이유가 없었다.

완료된 학생의 수만 카운트하는 방식으로 고쳤다.

'''
0번 학생부터 순회하며 연결 고리 찾기
'''

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

def dfs(i):
    global result
    
    visited[i] = True
    next = students[i]

    if not visited[next]:
        dfs(next)
    elif not finished[next]:
        j = next             # 현재 사이클 발생한 학생 번호 : j
        while j != i:        # 다시 경로 탐색하면서 그 사이클 길이 카운트 하기
            result += 1
            j = students[j]
        result += 1

    finished[i] = True

for _ in range(int(input())):
    n = int(input())
    students = list(map(lambda x: int(x)-1, input().split()))
    visited = [False] * n
    finished = [False] * n
    result = 0

    for i in range(n):
        if not visited[i]:
            dfs(i)

    print(n - result)