문제
https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을
www.acmicpc.net
주요 아이디어
처음에는 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를 재귀 대신 스택으로 구현하는 것도 좋은 선택인 것 같다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 13414. 수강신청 (0) | 2024.05.21 |
---|---|
[BOJ] 1806. 부분합 (0) | 2024.05.21 |
[BOJ] 12852. 1로 만들기 2 (0) | 2024.04.24 |
[BOJ] 1463. 1로 만들기 (0) | 2024.04.21 |
[BOJ] 12865. 평범한 배낭 (1) | 2024.04.21 |