문제 💁🏻♂️
해결 과정
[ 백준 10451 순열 사이클 ] 이 문제와 뭔가 비슷한 느낌이 들어서 그래프 알고리즘으로 큰 가닥을 잡았다. 이 문제에서 특이한 조건은 바로 팀을 정하는 방식이다.
- 스스로를 선택하여 1명이서 1팀을 이루는 조건
- 사이클이 존재(1 -> 3 -> 4 -> 1)하여 여러 명의 사람이 1팀을 이루는 조건
스스로를 선택하여 혼자 팀하는 경우는 어떻게 구현하면 되겠다는 생각이 바로 들었지만, 사이클이 존재하여 1팀을 이루는 경우에 대해서는 좀 생각하는 시간이 오래 걸렸다.
사고 과정 (1) ❗️
우선, 사이클을 판단해야 한다는 생각에 여러 그래프 알고리즘 중에서 DFS 알고리즘을 선택했다. 그 이유는 다음과 같다.
- 이 문제는 단방향 그래프이다. 즉, 한 노드에 여러 갈래가 존재하지 않고, 하나의 노드는 하나의 노드로만 향한다.
- 사이클이 존재한다면, 깊이 탐색하다보면 결국 자기 자신이 나타난다.
이와 같은 이유로 BFS말고, DFS 알고리즘을 사용하기로 마음 먹었다. 우선, 문제에서 주어진 입력을 받고, vertex 라는 새로운 그래프를 구현했다. 단방향 그래프이기 때문에 i -> v 로 그래프를 구현했다. 또한, 그래프 문제에서 필수 요소인 visited 리스트 즉, 방문 여부를 판단하는 리스트를 만들었다. 전체적인 구현 내용은 다음과 같다.
-
1번 노드부터 n번 노드까지 완전 탐색을 한다.
-
해당 노드에 방문한 적이 없다면
1) 방문 처리 이후, 자기 자신(For 출발점 비교 대상)과 자기 자신(For 노드 탐색)을 가지고 DFS 탐색을 실행한다.
2) DFS 탐색 과정은 방문할 수 있는 가능한 노드를 깊게 탐색한다.
3) 만약 자기 자신이 나타난다면 탐색한 모든 노드를 방문 처리한 상태로 냅두고, 자기 자신이 나타나지 않는다면 방문 처리한 것을 다시 복원 처리한다. -
모든 노드를 탐색한 이후, visited 리스트에서 아직 방문하지 않은 노드 번호가 바로 팀을 이루지 못한 인원이기 때문에 이를 카운트해서 반환한다.
결론적으로 지금까지 진행한 풀이는 80%에서 시간초과가 발생했다. 내 생각에는 학생의 수가 2 <= n <= 100_000 이기 때문에 최악의 경우 O(N^2)으로 10^10 연산이 이루어져 시간초과가 난 것으로 생각된다. 이를 어떻게 해결하면 좋을까 ?
사고 과정 (2) ‼️
이를 해결하기 위해서 많은 고민을 해보았지만, 해결하지 못하여 여러 블로그와 질문 게시판을 찾아보았다.
내가 놓친 부분은 사이클에 포함되지 않은 노드에서 시작하여 사이클이 발생한 경우를 생각하지 못한 것이다.
즉, 위 그림의 왼쪽처럼 사이클이 발생할 수도 있지만, 오른쪽 그림처럼 사이클에 포함되지 않는 1번 노드에서부터 시작해서도 사이클의 존재를 파악할 수 있던 것이다. 그렇다면 이를 어떻게 구현하면 좋을까? 이를 구현하기 위해서 유명한 백트래킹 문제인 N과 M 풀이에서 조금 따오면 가능했다.
-
1번 노드부터 n번 노드까지 완전 탐색을 한다.
-
해당 노드에 방문한 적이 없다면
1) 혼자 팀을 이루는 경우는 미리 방문 처리를 하며, 전체 인원 수에서 1을 뺀다.
2) 그게 아닌 경우에는 방문 처리를 해준 뒤,cycle이라는 리스트에 자기 자신을 담아 새롭게 만들어놓은 후에 DFS 탐색을 시작한다.
3) DFS 탐색에서는 다음 방문 가능한 노드를 cycle에 계속 추가해주면서 방문 처리를 해준다.
4) 그러다가 만약에 다음 노드가 이미 방문한 적이 있는 노드이면서, 현재까지 방문한 노드를 순서대로 저장한 cycle 리스트에 다음 노드가 존재하면 전체 인원 수에서 사이클의 길이만큼 빼준다. (index() 함수를 이용하는 테크닉이 필요하다.)
5) 방문한 노드는 맞지만, cycle 리스트에 존재하지 않는 노드 즉, 다른 DFS 탐색에서 이미 방문한 노드인 경우에는 그냥 return 해준다. -
DFS 탐색을 하면서 사이클을 이루는 사람들은 전체 인원 수에서 다 빼줬기 때문에 그냥 반환한다.
위 과정을 통해서 시간초과인 문제를 해결할 수 있었다!
코드
오답 코드 (오답 및 시간 초과)
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 5)
input = stdin.readline
def dfs(start, cur_x):
for nxt_x in vertex[cur_x]:
if start == nxt_x:
return True
if not visited[nxt_x]:
visited[nxt_x] = True # 방문 처리
flag = dfs(start, nxt_x)
if not flag:
visited[nxt_x] = False # 복원 처리
else:
return True
return False
t = int(input().rstrip())
for _ in range(t):
n = int(input().rstrip())
n_lst = list(map(int, input().split()))
vertex = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
for i in range(n):
vertex[i + 1].append(n_lst[i]) # i -> v 단방향
for i in range(1, n + 1):
if not visited[i]:
visited[i] = True # 방문 처리
flag = dfs(i, i)
if not flag:
visited[i] = False # 복원 처리
cnt = 0
for i in range(1, n + 1):
if not visited[i]:
cnt += 1
print(cnt)
정답 코드 (개선)
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 5)
input = stdin.readline
def dfs(cur_x):
global cnt
for nxt_x in vertex[cur_x]:
if visited[nxt_x]:
if nxt_x in cycle:
cnt -= len(cycle[cycle.index(nxt_x):])
return
else:
visited[nxt_x] = True # 방문 처리
cycle.append(nxt_x)
dfs(nxt_x)
t = int(input().rstrip())
for _ in range(t):
n = int(input().rstrip())
n_lst = list(map(int, input().split()))
cnt = n
vertex = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
for i in range(n):
# 혼자 팀을 이루는 경우 -> 미리 방문 처리
if n_lst[i] == i + 1:
cnt -= 1
visited[i + 1] = True # 방문 처리
vertex[i + 1].append(n_lst[i]) # i -> v 단방향
for i in range(1, n + 1):
if not visited[i]:
visited[i] = True # 방문 처리
cycle = [i]
dfs(i)
print(cnt)
Reference
