알고리즘) 프로그래머스 Graph, 가장 먼 노드

프로그래머스 고득점 Kit - Graph

가장 먼 노드

풀이

 

2020.04.25)

그래프를 이용해 푸는 문제다. 이에 LinkedList와 PriorityQueue(우선순위 큐)를 이용해 BFS로 문제를 풀었다. 마지막 depth의 노드 수를 구하는 것이기 때문에 BFS가 적절하다고 생각됐다.

 

1. 루트인 1부터 시작해서 연결된 노드를 탐색한다.

2. 우선순위 큐에 depth를 기준으로 정렬해서 BFS 탐색을 할 수 있도록한다. 이때, visit을 남겨서 depth를 설정할 수 있게 도왔다.

3. depth별로 노드의 수를 세면서, depth가 깊어질 때마다 노드의 수를 0으로 초기화 시켜줬다.

4. 마지막 depth에서 while문을 탈출하면서 노드의 수를 센 result가 return될 수 있게 설정했다.

 

2020.06.04)

오늘 풀었을 때는 우선 순위 큐를 이용하지 않고 풀었다.

노드를 먼저 연결한 뒤에, 루트인 1부터 연결된 노드를 탐색했다. 이 때, visit 배열을 이용하여 depth를 저장해주었는데, 8번과 9번이 통과되지 않았다. 그래서 검색해보니까 노드를 연결할 때, int형 말고 boolean으로 바꿔주니까 해결됐다는 글을 보았다.

그리고 다시 문제 조건을 보았는데 n이 최대 20000개였다... 최대 int형이 20000*20000 배열을 견딜 리가.. ㅠㅠ

그리고 다시 처음에 풀었던 코드를 보았다.

메모리와 속도 측면에서 훨씬 훌륭한 코드라고 생각한다.

DP 문제를 풀다보니, 배열을 쓰겠다는 생각이 먼저 들어서인지 배열로 시도한 것이 큰 착오였던 것 같다.

아무튼 풀기는 풀었지만 첫번째 풀이가 더 좋다고 생각한다.

 

 

코드 1

 

import java.util.LinkedList;
import java.util.PriorityQueue;

public class KitGraphFarthestNode {

    private static int solution(int n, int[][] edge) {
        LinkedList<Integer>[] nodes = inItList(n);
        nodes = makeNode(edge, nodes);

        return search(nodes);
    }

    private static LinkedList<Integer>[] makeNode(int[][] edge, LinkedList<Integer>[] nodes) { // 노드 이어주기
        for(int[] info : edge) {
            nodes[info[0]-1].offer(info[1]-1);    // 1~n 까지의 수 => 0~n-1까지 idx
            nodes[info[1]-1].offer(info[0]-1);    // 역방향은 이어주지 말자
        }
        return nodes;
    }

    private static LinkedList<Integer>[] inItList(int n) {	// LinkedList 초기화
        LinkedList<Integer>[] result= new LinkedList[n];
        for(int i=0; i<n; i++) {
            result[i] = new LinkedList<>();
        }
        return result;
    }

    private static int search(LinkedList<Integer>[] nodes) {
        PriorityQueue<MyNode> orderPQ = new PriorityQueue<>();	// 우선순위 큐를 통해 depth별 실행
        orderPQ.offer(new MyNode(0,0));	//root인 1부터 시작
        int[] visit = new int[nodes.length];
        visit[0] = 1;
        int depth =0;
        int result=0;

        while(!orderPQ.isEmpty()) {	// 
            MyNode node = orderPQ.poll();
            int cnt=0;
            if(depth != node.depth) {
                result =0;
                depth = node.depth;
            }
            while(!nodes[node.idx].isEmpty()) {
                int num = nodes[node.idx].poll();
                if(visit[num] ==0) {
                    visit[num] = 1;
                    orderPQ.offer(new MyNode(num, node.depth+1));
                    cnt++;
                }
            }
            if(cnt ==0) {
                result++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int n =6;
        int[][] edge ={{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};

        System.out.println(solution(n,edge));
    }
}

class MyNode implements Comparable<MyNode>{	// idx 번호와 depth 번호를 저장할 class
    int idx;
    int depth;

    public MyNode(int idx, int depth) {
        this.idx= idx;
        this.depth = depth;
    }

    @Override
    public int compareTo(MyNode o) {
        return this.depth > o.depth ? 1 : -1;
    }
}

 

코드 2

 

import java.util.LinkedList;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        // 간선 저장
        boolean[][] edges = new boolean[n+1][n+1];  // n이 20000개라서 int형 배열은 메모리 초과 (boolean은 가능..)
        for(int[] info : edge) {
            edges[info[0]][info[1]] =true;
            edges[info[1]][info[0]] =true;
        }
        
        // 탐색 list
        LinkedList<Node> list = new LinkedList<>();
        list.offer(new Node(1,0));
        
        // visit
        int[] visit = new int[n+1];
        visit[1] = 1;    // root
        int max =0;
        while(!list.isEmpty()) {
            Node node = list.poll();
            for(int i=1; i<=n; i++) {
                if(visit[i] ==0 && edges[node.idx][i]) {  // 연결된 노드 중, 방문한 적이 없어야
                    visit[i] = node.depth+1;
                    max = Math.max(max, visit[i]);
                    list.offer(new Node(i, visit[i]));
                }
            }
        }
        
        for(int i=1; i<=n; i++) {
            // System.out.print(visit[i] + " ");
            if(visit[i] == max) {
                answer++;
            }
        }
        return answer;
    }
}

class Node {
    int idx;
    int depth;
    
    public Node(int idx, int depth) {
        this.idx = idx;
        this.depth = depth;
    }
}