프로그래머스 3단계 - 가장 먼 노드 (Python, Java)

깃허브:

https://github.com/MSIQOC/Programmers/blob/main/%EA%B0%80%EC%9E%A5%EB%A8%BC%EB%85%B8%EB%93%9C.java

 

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

코딩테스트 연습 - 가장 먼 노드

 

20000*20000의 배열을 만드는건 메모리초과 때문에 안된다는걸 기억해야한다.

인접 행렬 대신 각 노드마다 연결된 노드만 저장시키는 인접리스트 방식을 사용해야한다.

자바에서 인접 리스트는 ArrayList를 이용해서 구현했다.

---

자바풀이

//
//  Created by MinSeo on 2021/08/31.
//  Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
//
import java.util.*;
class Solution {
    static ArrayList<Integer>[] pan;
    static int visited[];
    static int n;
    public static void bfs(int v){
        Queue<Integer> q = new LinkedList<>();
        q.add(v);
        visited[v] = 1;
        while(!q.isEmpty()) {
            for(int i=0; i<q.size(); ++i){
                int c = q.poll();
                for(int temp : pan[c]){ //c와 인접한 애들만 순회.
                    if(visited[temp] == 0){
                        q.add(temp);
                        visited[temp] = visited[c] + 1;
                    }
                }
            }
        }
    }
    public int solution(int nn, int[][] edge) {
        n = nn;
        int answer = 0;
 
        // 인접리스트에서는 arraylist로 선언
        pan = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) {
            pan[i] = new ArrayList<Integer>();
        }
        visited = new int[n+1];
        for(int i=0; i<edge.length; ++i){
            pan[edge[i][0]].add(edge[i][1]);
            pan[edge[i][1]].add(edge[i][0]);
        }
        bfs(1);
        Arrays.sort(visited);
        answer = 1;
        for(int i=n-1; i>=1; --i){
            if(visited[i] == visited[n]) ++answer;
        }
        return answer;
    }
}

---

파이썬풀이

"""
Created by MinSeo on 2021/08/31.
Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
 
"""
def bfs(visited, pan):
    q = []
    q.append(1)
    visited[1] = 1
    while q:
        v = q.pop(0)
        for e in pan[v]:
            if visited[e] == 0:
                visited[e] = visited[v] + 1
                q.append(e)
 
 
def solution(n, edge):
    answer = 0
    pan = [[] for _ in range(n + 1)]  # 어레이리스트 생성
    visited = [0] * (n + 1)
    for e in edge:
        pan[e[0]].append(e[1])
        pan[e[1]].append(e[0])
    bfs(visited, pan)
    for v in visited:
        if v == max(visited):
            answer += 1
    return answer

찾아본 결과 deque를 사용해서 푼 경우가 많지만 그러지 않고 그냥 일반 queue를 사용해서 풀면된다.