[PRO] 가장 먼 노드 | Java | Python

문제

프로그래머스 코딩테스트 연습 > 그래프 > 가장 먼 노드 | Lv.3

https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=java

프로그래머스

 

 

풀이 과정

자바와 파이썬으로 풀이하였습니다.

 

1. 자바 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n+1; i ++) {
            graph.add(new ArrayList<>());
        }
        
        // 인덱스에 해당하는 노드와 연결된 노드들 추가(양방향)
        for(int i = 0; i < edge.length; i++) {
            graph.get(edge[i][0]).add(edge[i][1]);
            graph.get(edge[i][1]).add(edge[i][0]);  
        }
        
        int[] visited = new int[n+1];
        
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visited[1] = 1;
        
        while(!q.isEmpty()) {
            int now = q.poll();
            for(int i = 0; i < graph.get(now).size(); i++) {
                int next = graph.get(now).get(i);
                // now와 연결된 노드들 순회하면서
                // next에 방문한 적 없으면 이전까지의 거리 + 1해서 저장 후 q에 추가
                
                if(visited[next] == 0) {
                    visited[next] = visited[now] + 1;
                    q.add(next);
                }
            }
        }
        
        int answer = 0;
        int max = 1;
        
        for(int i = 1; i <= n; i++) {
            if(visited[i] > max) {
                max = visited[i];
                answer = 1;
            } else if (visited[i] == max) {
                answer++;
            }
        }
            
        return answer;
        
    }
}

• bfs를 사용하였다.
• graph는 인덱스에 해당하는 노드 번호에서 갈 수 있는 노드들을 저장하고, visited는 해당 인덱스의 방문 여부 및 시작 노드(1)부터로의 거리를 저장하였다.
• 연결된 노드의 개수를 알 수 없어 ArrayList를 사용하였는데, 아직 사용에 헷갈리는 부분이 있어 get 사용은 구글링을 통해 도움을 얻었다.

 

 

2. 파이썬 풀이

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    visited = [0] * (n+1)
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    q = deque()
    q.append(1)
    visited[1] = 1
    
    while q:
        now = q.popleft()
        for next in graph[now]:
            if not visited[next]:
                q.append(next)
                visited[next] = visited[now] + 1
    
    answer = visited.count(max(visited))
    return answer