🌱 문제
https://www.acmicpc.net/problem/9466
예전에 시도했지만 잘 이해를 못한 채로 넘어갔고.. 다시 도전했다.
처음에 문제를 봤을 때에는 유니온파인드,, 로 풀어야 하나 싶었는데,,?
실은 이게 지금 BFS 분류 문제로 들어가 있어서 아닌 것 같긴 했지만,, (허헣 이렇게 풀면 안 되는데)
딱히 좋은 아이디어가 떠오르지 않았다.
그래서 또 해설 참고행...
다음에 또 다시 풀어보겠습니다..
참고한 출처 : (이 출처들에서 설명을 굉장히 자세히 해두셔서 이걸 보는 걸 더 추천합니다..)
🌱 접근 방식
거의 그냥 위 출처에서 설명해주신 것 정리지만,, 내 머리에 더 제대로 담기 위해 정리를 해보겠다..!!
먼저 알아야 할 것!
- 모든 원소는 어떤 원소를 가리키기 때문에, 이 가리키는 것을 타고타고 가다 보면 무조건 사이클이다!
- +) 이 글에서 접근 방법 자세히 써두었습니다
https://velog.io/@godqhrals/JAVA-%EB%B0%B1%EC%A4%80-17471-%EA%B2%8C%EB%A6%AC%EB%A7%A8%EB%8D%94%EB%A7%81
- +) 이 글에서 접근 방법 자세히 써두었습니다
그러면, 한 원소가 사이클인지 아닌지를 어떻게 알 수 있을까?
간단하게 시간복잡도 따지지 않고 생각해보자면,
이 원소가 사이클인 경우에는
아래와 같이, 자기 자신을 또 만나게 된다.
학생의 수가 N명일 때, 사이클의 크기는 최대 N이기 때문에
최대 N번 이내에 자기 자신으로 돌아오게 된다.
반대로 사이클이 아닌 경우에는, 자기 자신을 절대 다시 만날 수 없고!
자기 자신이 포함되지 않은 사이클 안으로 진입하게 되는데,
이 사이클 안을 돌다가 이미 방문한 노드를 만나게 된다.
그런데 이 아이디어만 가지고 진행하다보면 시간복잡도가 너무 커진다는 단점이 있다.
크기 N만큼의 사이클이 있는 상황이라면
모든 학생들이 N번 이동을 진행해야 해서 시간 초과가 뜬다. -> O(n^2)
그리고 이미 방문한 루트를 또 방문해야 한다는 단점이 있다.
아래 그림에서 y에서 y -> z -> 저 사이클 이 경로로 이미 갔는데,
x에서 x -> y -> z -> 저 사이클 경로로 또 가려고 하니까 중복이 발생한다.
🔥
그래서!! 이전의 방문을 이용하는 아이디어가 필요하다!
아래와 같이 방문 표시를 남기면서 가면,
재방문이 된 경우에는 사이클에 포함되어 있다는 뜻이고,
재방문이 안 되면 사이클에 포함되어 있지 않다는 뜻이다.
이때, 재방문이 된 경우에 대해(즉, 사이클을 찾은 경우에 대해)
그 학생에서 다시 출발해서 사이클을 한 바퀴 돌면서
지금 방문하는 학생들이 전부 사이클에 포함된 학생이라는 표시를 남기면서 이동한다.
그리고 남아 있는 학생들(노란색 부분)은
사이클에 포함되어 있지 않은 학생이라는 표시를 남기면 되는데,
초록색 박스 노드에서 사이클에 포함된 노드를 만날 때까지 다시 한 번 다음 노드로 이동해주면 된다.
그 후에는, 이 기록들을 확인하면서 작업하면 된다.
아래 그림에서, 1,2번대로 방문하다가 3에서 이미 사이클인 노드를 만나게 되면,
지금까지 방문해온 1,2는 사이클이 아니라는 사실을 알게 된다.
그러면, 이 1,2도 사이클x로 기록해주면 된다.
그리고, 이미 사이클x 로 기록되어 있는 노드를 만나면,
자기 자신도 사이클이 아니라는 사실을 알게 되어서 사이클x로 기록해주면 된다.
그래서
임의의 학생 A에서 시작해서 다음 학생으로 계속 이동할 때,
1) A를 사이클o로 기록하는 경우
- A를 재방문하는 경우
- 이때 A에서 한번 더 다음 학생으로 이동하면서 A에 다시 도착할 때까지 만나는 학생들을
사이클o로 기록한다.
- 이때 A에서 한번 더 다음 학생으로 이동하면서 A에 다시 도착할 때까지 만나는 학생들을
2) A를 사이클x로 기록하는 경우
- 이미
사이클o인 학생을 재방문한 경우 - 이미
사이클x인 학생을 재방문한 경우 - A 자신이 아닌, 다른 학생 B를 재방문한 경우
- (B 입장에서 1)
사이클o로 기록하는 경우) 이때 B에서 한번 더 다음 학생으로 이동하면서 B에 다시 도착할 때까지 만나는 학생들을사이클o로 기록한다. - A에서 다음 학생으로 이동하면서 B에 도착할 때까지 만나는 학생들을
사이클x로 기록한다.
- (B 입장에서 1)
이를 정리하면,
임의의 학생 A에서 시작해서 다음 학생으로 계속 이동할 때,
1) 이미사이클x또는사이클o인 학생을 재방문하면 -> 지금까지 방문한 학생들을사이클x로 기록한다.
2) A를 재방문하면 -> A에서 한번 더 다음 이때 A에서 한번 더 다음 학생으로 이동하면서 A에 다시 도착할 때까지 만나는 학생들을사이클o로 기록한다.
3) A 자신이 아닌, 다른 학생 B를 재방문하면 -> B에서부터 출발해서 2번 과정 진행! 그리고 A에서 다음 학생으로 이동하면서 B에 도착할 때까지 만나는 학생들을사이클x로 기록한다.
=> 각 학생을 최대 2번 방문하게 되어서 O(n)이다.
이때, 임의의 학생 A에서부터 시작해서
이전에 방문한 값 C를 재방문했을 때,
이번 방문에서 방문된 값인지(-> 이러면 C에서부터 시작해서 사이클o라고 기록해야 하고, A는 사이클x라고 기록해야 함)
예전 방문에서 방문된 값인지(-> 이러면 그냥 바로 A는 사이클x라고 기록하면 됨)
구분할 수 있어야 한다.
아래 그림에서 지금 방문하는 학생이 1번 학생이면,
지금부터 방문하는 노드들을 1로 기록하면서 진행하다가
핑크색 박스 노드를 다시 한번 더 방문하게 되었는데, 이게 1번 시작 방문임을 깨닫고 사이클임을 찾아낼 수 있게 된다.
아래 그림과 같이, 만약 기록된 숫자가 다른 것을 찾게 된다면,
이번 방문이 아니니까 1번 케이스여서
지금까지 방문한 애들을 바로 다 사이클x로 기록하면 된다.
=> 이렇게 방문 숫자를 관리해주면 더 케이스 분류가 덜 복잡해지고 코드가 간결해진다고 한다.
🌱 풀이
아,, 원리는 그림으로 다시 일일이 그려보면서 이해했는데 코드로 구현하려니까 어려웠다...
으엇 결국 정답 코드 참고해서 이해했는데
진짜 다음에 스스로 힘으로 다시 풀어보겠습니다..
import java.util.*;
import java.io.*;
public class Main {
static final int NOT_VISITED = 0;
static final int IN_CYCLE = -1;
static int n;
static int[] select, state;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int tc = 0; tc < t; tc++) {
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
select = new int[n + 1];
state = new int[n + 1];
for (int i = 1; i <= n; i++) {
select[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= n; i++) {
if (state[i] == 0) run(i);
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (state[i] != IN_CYCLE) cnt++;
}
sb.append(cnt).append("\n");
}
System.out.println(sb);
}
static void run(int x) { // x = 몇 번 학생에서 출발한 것인지!
int cur = x;
while (true) {
state[cur] = x;
cur = select[cur]; // 다음 것
// 이번 방문에서 지나간 학생에 도달했을 경우 -> 사이클 o
if (state[cur] == x) {
while (state[cur] != IN_CYCLE) {
state[cur] = IN_CYCLE;
cur = select[cur];
}
return;
}
// 이전 방문에서 지나간 학생에 도달했을 경우
if (state[cur] != NOT_VISITED) {
return;
}
}
}
}