- 문제
최단 거리의 경우 크리티컬 포인트가 while을 한 번 순회하는 것을 count++ 즉, 한 정점에서 다른 정점으로 가는 것으로 가정.(그래서 count는 -1이 디폴트) stack과 queue를 이용해서 매번 queue를 검사한다. 그리고 방문 노드의 인접 노드들을 동시에(내가 이해한 것으로는) 탐색해서 도착지와 queue에 들어있는 인접 노드가 같으면 count를 반환하는 식으로 했다. 그렇다면 최장 거리는 어떻게 해야 할까.
- 내 풀이
그림으로 나타내면 이런 식인데 1에서 7로 가는 경우가 엄청 많다.
2021.02.07 못 품
- 답안
윽 너무 어렵다 최장거리... dfs bfs에 재귀까지 들어가니까 머리가 안 따라간다. 일단 답안을 분석해보자!
- 답안 분석
const start = 1;
const end = 7;
let queue = [start];
let visited = [];일단 전역에 시작 노드, 끝 노드 선언, 할당하고 queue에 시작 노드를 visited는 빈 스택으로 둔다.
let node = n[n.length - 1];
let length = 0;node는 n(queue)의 마지막 요소로 할당하고 length라는 변수를 선언, 할당한다!
if (node == end) {
return visited.length;
}최단 거리와 마찬가지로 도착지가 node라면 visited.length의 반환!
if (visited.includes(node)) {
return visited.length;
} else {
visited.push(node);
}visited 스택에 node 가 있다면 visited.length 반환! 아니라면 visited 스택에 node를 추가한다!
최단 경로와 다른 로직은 visited 스택에 node가 없으면 push했는데 최장 경로는 node가 없으면 push하고 있으면 length를 반환(함수 종료)를 하는 것!
let max = [];
for (let next_node in graph[node]) {
n.push(graph[node][next_node]); // (1)
max.push(length, sol(n, visited)); // (2)
length = Math.max.apply(null, max); // (3)
queue.pop(); // (4)
}max라는 배열을 선언한다! 이 배열이 중요하다! 이제 graph[node] 를 for in해서 인접 노드을 검사한다!
(1) 에서 n에 일단 인접 노드들 graph[node][next_node]를 넣는다.
(2) 에서 max라는 배열에 length와 재귀함수를 넣는다 --> 어려워!!
(3) 에서 length에 다시 할당하는데 max 배열에에서 가장 최장 경로인 것을 찾는다.
(4) 에서 queue에서 하나를 빼면 for문 종료
return length;그렇게 최장 경로를 리턴하면 되는데 어떤 플로우인지 감이 안 온다.
- 포기하지 마 김동하
하나씩 차근차근 하다 보면 다 된다. 차근차근 해보자!
node = 1
node 1이다. 그렇다면 end랑 같다 조건, visited에 포함 조건도 해당되지 않기 때문에 visited에 넣고 for in으로 넘어간다. next_node는 일단 2다. n에 2를 넣고 max length(현재는 0)과 재귀를 넣는다. 그러면 재귀가 실행!
이제 node는 2다. visited는 [1, 2]. for in에서 2의 인접 노드는 1. n에 1 넣고 max에 넣으면 다시 재귀가 실행!
이제 다시 node는 1. 이번에는 visited에 1이 있기 때문에 if에서 걸린다. return은 visited.length 즉, 2다. 재귀 탈출해서 max = [0 , 2]가 있다. length는 2로 다시 할당되면서 한 턴이 드디어 끝난다.
이제 남은 재귀 친구들을 해결해야 한다. 다음 인접 노드는 3. for in에서 n에 3을 넣고 n은 현재 [1, 2, 3]. 뭐 좀 해보려고 했으나 max에 푸시당하고 재귀에 걸려서 다시 처음으로.
max 배열에 푸시해서 재귀를 돌 때마다 length가 초기화된다. 이렇게 모든 경우의 length를 비교하는구나!
node는 3, length는 0. visited에 [1, 2, 3]. for in문에서 next_node는 또 1. 재귀를 돌고 node가 1 되면서 재귀 탈출하고 visited는 3되고 이렇게 쭉쭉 하나씩 검사를 하는구나
- 결론
dfs, bfs, 재귀까지 너무 어려운 개념들 총집합이라 일단 일보 후퇴를 하고 다시 도전하기로 했다. 하지만 어느정도 어떻게 돌아가는지 알았으니 양치질 할 때도, 점심 먹을 때도, 자기 전에도 늘 생각하다 번뜩이는 순간에 풀어야지. 파이팅 김동하!
출처: 제주코딩캠프
