작성자님께서 말씀하시는 "mid값보다 크면"이 DFS 함수 내의 얘기인지, 아니면 main 함수에서의 얘기인지 구분이 잘 되지 않으므로 2가지 경우로 나눠서 설명하겠습니다.

1. 주어진 DFS 함수 내에서, 처음 선택한 다리보다 더 튼튼한 다리가 존재한다면
   → 제시해 주신 코드는 이분탐색으로 최대 무게를 찾는 방식이기에, DFS 함수가 실행되는 동안의 midval은 고정되어 있습니다.
   즉, 매우 튼튼한 다리든, 매우 부실한 다리든, DFS 함수 내에서는 midval의 무게를 견뎌내기만 하면 됩니다.
   주어진 DFS 함수의 역할은, 출발지점에서 목적지점까지 midval만큼의 무게를 가진 채로 도달할 수 있는지의 여부를 확인하는 것, 그 이상도 그 이하도 아닙니다.
   따라서, A에서 B로 가는 다리들 중에서 midval보다 큰 다리가 여러 개가 있다 해도, 방문 여부를 false로 변경하고 다시 돌아갈 필요가 없습니다.
   어차피 midval의 값은 고정되어 있습니다.
   
   
2. main 함수에서, DFS 함수가 반환한 값에 따라 새로운 midval을 정한 뒤, 다시 DFS 함수를 실행한다면
   → 이 경우를 걱정하셔서 방문했던 장소의 방문 여부를 false로 변경하신 거라면, 걱정하실 필요가 없습니다.
   작성자님께서 midval을 while문에서 매번 변경하듯이, 방문 여부를 확인하는 read도 매번 새로 할당되니까요.

아 제가 질문을 잘못 썼네요.. dfs를 이용해 고정된 mid보다 크거나 같은 경로를 탐색하다가 mid보다 작은 다리를 만나게 되면 그 다리는 false 처리를 해줘야 한다고 생각했습니다. 그래야 같은 mid값을 기준으로 현재 이 다리를 건너야 하는 경우에 문제없이 건널 수 있다고 생각했습니다.

-------10------> O -------5------->

-------7------>       

위와 같은 그래프가 있을 때(3이 5와 연결된 상태),   midval이 9이고, 10에서 5로 향하는 길을 갔다가, 실패하게 된다면 7에서 시작하는 경로도 찾아야 할것입니다. 그럼 이전에 5를 갔었던 기록을 지워야 7에서 5에서의 경로를 지날 수 있는 것 아닌가요???

어... 질문자님이 올려주신 그래프가 제대로 나오지 않으며, 말씀하시는 함수의 방식이 잘 이해가 되지 않네요.

올려주신 코드의 DFS함수의 작동 방식은 다음과 같은 것 같습니다.

0. 출발지를 대상으로 DFS 함수를 실행한다.

1. 섬curidx의 방문 기록을 true로 한다.
2. 섬curidx와 연결된 다리들 중, midval보다 크거나 같은 중량제한을 가진 다리이면서, 아직 방문하지 않은 섬과 연결된 다리를 선택해, 그 다리와 연결된 섬을 대상으로 다시 DFS 함수를 실행한다.
3. (문제가 되는 부분) 섬curidx와 연결된 다리들을 모두 확인하고 나면, 섬curidx의 방문 기록을 false로 바꾼다.
4. 만약 섬curidx가 목적지라면 함수를 종료하고 midval을 더 크게 잡은 뒤, 0번 과정으로 돌아간다.
5. 만약 목적지를 방문하지 못하면 함수를 종료하고 midval을 더 작게 잡은 뒤, 0번 과정으로 돌아간다.

일단 시간초과가 되는 경우는 이런 경우가 있을 것 같네요.

A와 목적지를 연결하는 다리가 80000개, A와 (A, 목적지를 제외한)섬 9998개가 각각 다리 1개, 출발지와 (A, 출발지, 목적지를 제외한)섬 9997개가 각각 다리 1개로 연결되어 있을 경우입니다.

만약 위와 같은 상황이라면, midval을 갱신할 때마다 매번, 최악의 경우, 약 8억번의 연산을 하게 됩니다.

각 섬에 갈 때마다 A로 가고, A에서 목적지로 가는 다리 8만개를 확인해야 하기 때문입니다.

그러므로 방문 기록을 false로 변경하게 되면 시간초과가 발생하게 됩니다.

"그렇다면 방문 기록을 false로 안 바꿔도 되는가?" 라는 의문이 발생하실 수 있습니다.

예, 괜찮습니다.

위의 코드를 간략화하면 이렇습니다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

"이 무게로 목적지까지 갈 수 있을까?"

O -> 그럼 더 무겁게 해서 다시 확인해야지

X -> 그럼 더 가볍게 해서 다시 확인해야지

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

앞서 말씀드렸듯이, midval이 갱신될 때마다 모든 방문기록도 전부 초기화되기 때문에, '이전 DFS 함수에서 방문했던 섬이라서 방문을 안 하는 건 아닐까' 하는 고민은 없습니다.

또한, 어차피 midval은 DFS 함수 내에서 고정되어 있기 때문에, 특정 경로를 통해 출발지에서 섬A까지 갈 수 있었다면, 섬A까지 갈 수 있는 다른 경로를 고민할 필요가 없습니다.

이미 갈 수 있다는 걸 알기 때문입니다.

주어진 DFS 함수의 역할은, 주어진 midval을 가지고 목적지에 도착할 수 있는지 확인하는 겁니다.

절대, 최적의 경로를 찾는 게 아닙니다.