[프로그래머스] lv3. 가장 먼 노드 [#그래프]

 

 

 

---

1. 문제 출처

---

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

프로그래머스

 

시작 시간 : 오후 8시 45분

종료 시간 : 오후 9시 23분

---------------------------------

38분 경과

 

 

 

 

---

2. 설계 및 코드

---

 

문제 이해

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하는 문제이다.

즉, 1번으로부터 연결된 간선이 많은 노드를 찾는 문제이다.

 

입출력

순서대로 int n, int[][] edge, 결과값이다.

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

 

설계

1. 연결 노드를 큐에 적재 (노드번호, ORDER)
2. 큐에서 Node를 꺼낼 때 마다 order이 큰 녀석으로 갱신

 

코드

//1번 노드에서 가장 멀리 떨어진 노드의 갯수 (간선)
//1. 연결 노드를 큐에 적재 (노드번호, ORDER)
//2. 연결된 간선이 없는 노드를 발견하면 order 큰 녀석으로 갱신
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    
    public static class Node implements Comparable<Node>{
        int node;
        int order;
        public Node(int node, int order){
            this.node = node;
            this.order = order;
        }
        
        @Override
        public int compareTo(Node o){
            return this.order>o.order?1:-1;
        }
    }
    
    static ArrayList<Node>[] adj;
    static int count=0;
    
    public int solution(int n, int[][] edge) {

        adj = new ArrayList[n+1];
        for(int i=1;i<n+1;i++){
            adj[i] = new ArrayList<>();
        }
        
        for(int i=0;i<edge.length;i++){
            //양방향
            adj[edge[i][0]].add(new Node(edge[i][1],0));
            adj[edge[i][1]].add(new Node(edge[i][0],0));
        }
        
        far(n);
        
        return count;
    }
    
    public static void far(int n){
        Queue<Node> q = new LinkedList<>();
        boolean[] visited = new boolean[n+1];
        int max_order=0;
        
        //첫 노드 넣기
        q.offer(new Node(1, 0));
        visited[1] = true;
        
        while(!q.isEmpty()){
            Node cur = q.poll();
            
            
            if(max_order<cur.order){
                max_order=cur.order;
                count=1;//새로운 order
            }else if(max_order==cur.order){
                count++;//기존 order
            }
            
            
            for(int i=0;i<adj[cur.node].size();i++){
                Node next = adj[cur.node].get(i);
                if(visited[next.node]) continue;
                
                visited[next.node] = true;
                q.offer(new Node(next.node, cur.order+1));
            }
        }
        
    }
}

 

헤맨 이유

static ArrayList<Node>[] adj;

Node 타입이 아닌 Integer 타입으로 했다가 

 

Node next = adj[cur.node].get(i);

int next에 넣어줄라니 Integer는 int로 타입 변환 될 수 없다고 마주했다...

 

결국 다시 Node 타입으로 진행

 

 

if(max_order<cur.order){
	max_order=cur.order;
	count=1;//새로운 order
}else if(max_order==cur.order){
	count++;//기존 order
}

order 갱신 부분도 사실 연결된 간선이 없는 노드를 만나면 갱신해주려고 했으나 양방향 그래프이기 때문에 간선이 있는 노드도 마지막 노드가 될 수 있다는 사실을 깨달았다. 때문에 큐에서 노드를 꺼낼 때 마다 비교해서 갱신해주었다.