[BOJ] 9466. 텀 프로젝트

문제

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

9466번: 텀 프로젝트

 

---

 

주요 아이디어

처음에는 BFS 방식으로 접근하고자 했다.

1. BFS를 수행해 그래프가 완성되는지 판단

2. 그래프가 완성될 경우 그래프에 속한 노드를 반환 / 아닐 경우 None을 반환

3. 시작 노드 순차적으로 순회하며 BFS를 수행하고, 그래프가 만들어진 노드들의 개수를 제하면 그래프가 완성되지 않은 노드들의 개수만 남게 됨

 

---

 

코드 구현 (Python 3)

 

# 시작 노드로부터 간선 연결 가능
from collections import deque

# 그래프 형성될 경우 그래프에 속한 노드 반환
# 아닐 경우 None 반환
def bfs(graph, start):
    queue = deque()
    visited = [start]
    queue.append(start)

    while queue:
        now = queue.popleft()
        
        # 단 한명만 선택 가능
        if graph[now] not in visited:
            queue.append(graph[now])
            visited.append(graph[now])

        # 시작 지점으로 돌아왔다는 뜻
        if graph[now] == start:
            return visited
    
    return None


T = int(input())

for _ in range(T):
    n = int(input())
    graph = dict()

    numbers = list(map(int, input().split()))
    
    # number들을 딕셔너리에 추가해주기
    for idx, num in enumerate(numbers):
        graph[idx + 1] = num

    group_node = []

    # bfs 수행하기 - 시작 노드 순차적으로 넣어주기
    for start_node in range(1, n+1):
        if start_node not in group_node:
            group = bfs(graph, start_node)
            if group != None:
                group_node += group

    # print('## total group node : ', group_node)
    print(n-len(group_node))

 

하지만 결과는 시간 초과..

 

---

 

실패 원인

구글링 결과 매번 visited 배열을 초기화해주는 데에서 시간초과가 나는 것 같다.

그리고 보편적인 풀이는 DFS를 통해 그래프 완성 여부를 판별하는 것 같아서, 재구현시에는 DFS로 풀었다.

 

+) 추가 : BFS로도 시간 초과 나지 않고 잘 푸는 방법이 아래 포스팅에 소개되어 있다

https://velog.io/@jollidah/백준-9466번-텀-프로젝트-Python

핵심은 매번 group을 초기화해주는 것이 아니라, BFS 동작 밖에서 선언해주고 add, remove를 하는 것이다.

 

---

 

코드 재구현 (Python 3)

import sys

sys.setrecursionlimit(10**5)

def dfs(node):
    global cnt

    visited[node] = True
    group.append(node)

    # 방문 지점으로 돌아왔다면
    if visited[graph[node]] == True:
        # 사이클이 완성되었을 경우
        if graph[node] in group:
            # 전체 그룹에서 슬라이싱해주기
            cnt -= len(group[group.index(graph[node]):])
        return
    else:
        dfs(graph[node])



T = int(input())

for _ in range(T):
    n = int(input())
    graph = [0] * (n+1)

    numbers = list(map(int, input().split()))
    
    # 인덱스 = 선택하는 학생, 값 = 선택되는 학생
    for idx, num in enumerate(numbers):
        graph[idx + 1] = num

    cnt = n
    visited = [False] * (n+1)
    result = []

    # dfs 수행하기 - 시작 노드 순차적으로 넣어주기
    for start_node in range(1, n+1):
        if visited[start_node] == False:
            group = []
            dfs(start_node)

    print(cnt)

 

---

 

제출 결과

 

참고로 보편적으로 쓰이는 sys.setrecursionlimit(10**6) 를 사용했을 때 메모리 초과가 발생해서  sys.setrecursionlimit(10**5) 를 사용했더니 통과가 되었다!

재귀 형식으로 DFS 문제를 풀 때에는 이 부분도 유의하면 좋을 것 같다.

---

 

코드 개선 방안

BFS로 끝까지 풀이해보지 않은 점이 살짝 아쉽다. 또한 복잡도 측면에서 봤을 때 DFS를 재귀 대신 스택으로 구현하는 것도 좋은 선택인 것 같다.