반례 데이터 먼저 들어드릴게요.

1

7

7 6 7 6 6 7 3

답 5

프로그램에서 출력하는 코드 3

이게 맞은 거 같지만 틀린 이유를 세세하게 분석해 볼게요.

dfs (1)과 dfs (2)는 볼 게 없습니다. dfs (3)을 볼게요.

반례 찾기가 무쟈게 어려워서. 잠재적인 문제점 먼저 찾기로 했습니다.

check[x]. 이게 뭔지는 정확히 모르겠지만, 코드를 보니, 2가지 일을 수행한다고 생각이 되는군요.

(1) 현재 x번 위치에 있을 때, 어디서부터 왔는지를 저장한다.

(2) x을 이전에 방문했는가? 그렇지 않은가?

이런 경우, 잠재적인 문제가 발생할 위험이 있는데요. 안 그래도, 하나의 배열에 복잡한 기능 2개가 들어가 있습니다. 실수하기 딱 좋죠.

물론, 반례를 찾기도 매우 매우 어려우셨으리라 생각됩니다.

dfs(3) 먼저 호출해 봅시다. (2)로 인해, 처음에 check[3]은 0이 될 겁니다.

그리고 dfs(3)이 호출되겠죠. 그리고 님 의도에 따라서 dfs(7)이 호출될 겁니다. 그리고 dfs(3)이 호출되고.

님이 작성하신 사이클 detect 알고리즘에 의해서 제대로 동작하겠지요.

문제는 dfs(4)가 호출될 경우입니다.

dfs(4), dfs(6) 순으로 탐색합니다. 그리고 뜬금없이 dfs(7)을 호출하는데요.

dfs(6)을 기준으로 봤을 때, arr[x]는 7이죠. dfs(7)이 호출 되었을 때

66번째 else문에 의해서 빠져나옵니다. 그리고, dfs(6)으로 돌아오겠죠. (호출 스택을 그려보세요.)

그러면, flag가 false 이므로, 71번째 줄을 수행할 텐데요.

여기서 check[7]이 0으로 되어버립니다. 이미 탐색한 노드가 탐색 안 했다고 덮어 씌워지는 것이지요.

그 다음에 dfs(5)를 호출해 봅시다.

7이 방문 안 했다고 되어 있으므로, 5, 6, 7, 3 순으로 탐색합니다.

3은 탐색 했다고요? 그건 중요하지 않습니다. 3이 탐색을 했건, 그렇지 않건, 일단 dfs(arr[i])에 의해서

무조건 7과 인접한 노드인 3은 탐색하게 되어 있고요.

dfs(3) 함수 호출이 끝나면 check[3]이 0으로 덮어 씌워지겠지요. 탐색되었던 것들은 모두 0으로 덮어 씌워지고요.

다음, dfs(6)을 호출해 볼까요?

이 경우, 6, 7, 3, 7 순으로 호출이 될 텐데요. 이 경우는 더 이상하게 동작합니다.

temp가 6이였습니다. check[7] == 6이니. 이건 맞습니다. 그러나, x가 temp는 아니죠. 고로 58번째 줄은 쿨하게 패스하고요.

else문을 수행함으로써, 왔던 길 모두가 지워져 버리는군요.

그러니까 dfs(7)을 호출하면

7, 3, 7 이렇게 호출한 후에, 사이클을 중복해서 세는 것이지요.

정확히 말하면 70에서 71번째 줄이 문제입니다.

한가지 더 문제점이 있다면 이 코드로 몇 %까지는 Accept 받는다고 쳐도

TLE를 받으실 가능성이 굉장히 높다는 것인데요. 저렇게 하면 O(n^2) 정도 되죠. 최악의 경우에.

1

100000

2 3 4 5 6 7 8 9 ... 100000 100000

이 경우에 min님 알고리즘이 인접 노드 탐색 연산을 몇 번 하는지 잘 생각해 보세요.

제가 min님 알고리즘을 세세하게 분석한 걸 보신다면, 어떻게 필요 없는 계산을 많이 하는지 아실 듯 싶네요.

공간 더 쓰셔도 실행 시간이 화끈하게 늘어나진 않으니 (배열을 엄청나게 길고 크게 선언하면 모를까)

방문했는지 판단하는 기능, 몇 번째 노드부터 시작했는지 역추적을 위한 기능. 이 2개를 분리시키는 게 좋을 듯 싶네요.

와... 정말 세세한 답변 감사드립니다 ㅠㅜㅜㅜㅜㅜㅜㅜ

덕분에 뭐가 문제인지는 파악이 가능해졌네요 ㅠㅠ 진짜 감사드려요!!!