[Java] 가장 먼 노드

문제 접근법1 (DFS 시간초과) 이 문제는 BFS로 풀면 될것 같았지만, 최근 백트래킹을 연습하고 있어서 한번 시도해보았다. 백트래킹으로 풀때 고려해야할 사항은 특정 조건일때만 탐색을 지속해서 하는 것인데, 이 코드에서는 그 조건을 거리로 기준 잡았다. 문제에서 요구하는 것은 최소 거리를 찾는 것이다. dfs를 사용하면 고려해야할 사항이 있다. 특정 노드에 도착했을때, 본인의 경로가 다른 곳을 경유했는지, 아니면 바로 방문했는지이다. 예를들어 예제 같은 경우는 1번에서 시작해 2번으로 가는 경우가 세 가지 있다. 1->2 직접 가는 경우 1->3->2 3을 경유해가는 경우 1->3->4->2 3, 4를 경유해가는 경우 우리가 문제에서 구하고자 하는 것은 1번 케이스이다. 따라서, 그 외의 경우일때는 탐색을 하지 않는다. 첫번째 방문을 했을때 hashDistance에 경로를 담아두고, 처음 담아둔 경로보다 작을때만 로직을 진행한다. 이를 코드로 표현했을때, 다음과 같았다. if(ha...

원문링크 : [Java] 가장 먼 노드