49189: 가장 먼 노드

Link : https://programmers.co.kr/learn/courses/30/lessons/49189

---

1. 문제

• n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
  노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

---

2. 문제의 조건

• 2 <= node <= 20,000 (노드 개수)
• 간선 양방향 1 <= cnt <= 50,000

 

---

3. 문제 접근

• 아이디어
  
  해당 문제는 간선의 가중치가 없습니다. 만약 간선의 가중치가 존재한다면 다익스트라로 해결이 가능하겠습니다!!
  다익스트라로도 해당 문제가 해결이 가능하긴 합니다만 굳이 필요 없습니다.
  해당 문제는 예제를 보면 알겠지만 최선의 방법으로 가장 먼 노드에 도착해야합니다.
  저는 너비탐색인 BFS와 방문변수인 visited를 이용하여 중복을 제거하여 탐색하였습니다.
  만약, 이미 방문한 자리를 또 한번 방문하려고 시도하면 continue를 이용하여 패스하였고 만약 a -> c로 갈 수 있는 방법은 a -> b -> c, a -> d -> e -> c가 존재한다면 현재 지점 c가 최소인지 판별하고 최소이면 탐색을 계속하고 최소가 아니면 그 자리에서 탐색을 중지합니다. 즉 distance변수도 만들어줍니다.
  
  마지막으로 해당문제는 양방향이므로 저는 편리한 인접리스트를 이용하였습니다.

 

---

4. 풀이 방법

• 인접리스트 2차원 배열을 선언한다.
• BFS를 사용하기 위한 que를 만들어준다. (BFS를 효율적으로 구현하기 위해 deque로 선언하였음)
  일반적인 python에서 지원하는 queue의 pop(0)은 O(n)의 시간이 소요됨.
• 거리 배열과 방문 배열을 만들어줌.
• 인접리스트를 양방향으로 데이터를 받음.
• que에 (현재시작점, 현재거리)를 등록해줌. 이를 now_pos, now_stack으로 표시함
• que가 빌 때 까지 계속 반복함.
• 맨 왼쪽에 있는 que를 꺼내오고 방문했는지 확인함.
  만약 방문했으면 continue로 건너뜀.
• 방문하지 않았으면 해당 방문지점을 True로 만들어줌
• 그리고 현재 시작점으로부터 갈 수 있는 곳을 확인함.
  만약 지금 도달한 거리보다 이미 방문한 최소경로가 있다면 건너뜀
• 현재가 최소경로이면 distnace는 now_stack + 1로 하고 que에 마찬가지로 등록해줌.
• que가 종료되면 distnace[0]번째는 INF이므로 제외하고 그와중 최대값을구함.
• 그리고 최대값을 리턴해주면 해결가능.

 

---

5. 소스코드

• https://cjw-git.tistory.com/176

 

---

 

cjw.git@gmail.com