[알고리즘] 프로그래머스 가장 먼 노드 -그래프- 자바

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

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

 

 

 

최근 백준만 풀다가 오랜만에 프로그래머스 문제를 풀어본 것 같습니다. 예전에는 프로그래머스에 적응이 되어 백준의 입력값을 직접 받아야한다는점이 거부감이 있었는데 이제 프로그래머스가 뭔가 어색하네요. ㅎㅎ

 

프로그래머스 고득점 kit 그래프 종류에 있던 Level 3 문제입니다.

최단경로 문제인가 했는데 최단 경로가 아닌 최장 경로의 개수가 몇개인지 묻는 문제이고 간선의 가중치는 1로 모두 동일하다는 특징을 갖고 있습니다. 

 

저는 평소 최단경로 문제푸는거에서 살짝 변형해서 풀었고 BFS 탐색을 사용했습니다. 푼 후 다른 분들의 풀이를 보니 Node와 같은 클래스 필요없이 그냥 Integer 리스트로 풀 수 있는 것 같더라고요. 

 

 

풀이는 다음과 같습니다.

1. 간선 리스트를 만든다.

2. BFS 탐색한다.

자세한 사항은 주석에 설명해놨습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    private static boolean[] check;
    private static List<Edge>[] nodeList;

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(6, new int[][]{{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}});
    }

    public int solution(int n, int[][] edges) {
        int answer = 0;
        check = new boolean[n + 1];
        nodeList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            nodeList[i] = new ArrayList<>();
        }
        Queue<Edge> queue = new LinkedList<>();
        //간선 리스트 생성
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            nodeList[a].add(new Edge(b, 0));
            nodeList[b].add(new Edge(a, 0));
            if (a == 1) { //시작점인 1을 큐에 넣는다.
                queue.offer(new Edge(b, 1));
                check[b] = true;
            }
            if (b == 1) { //시작점인 1을 큐에 넣는다.
                queue.offer(new Edge(a, 1));
                check[a] = true;
            }
        }
        check[1] = true;
        int max = Integer.MIN_VALUE;
        //2. BFS 탐색
        while (!queue.isEmpty()) {
            Edge prevEdge = queue.poll();
            if (max == prevEdge.weight) { //최댓값과(최장경로) 같은 값이 들어온 경우 answer + 1 을 해준다.
                answer += 1;
            } else { //새로운 최장 경로가 들어온 경우 answer 을 1로 초기화 해준다.
                answer = 1;
                max = prevEdge.weight;
            }
            for (int i = 0; i < nodeList[prevEdge.vertex].size(); i++) { //현재 노드에 이어진 다음 노드 큐에 넣는다.
                Edge nextEdge = nodeList[prevEdge.vertex].get(i);
                if (!check[nextEdge.vertex]) {
                    check[nextEdge.vertex] = true;
                    queue.offer(new Edge(nextEdge.vertex, prevEdge.weight + 1));
                }
            }
        }
        return answer;
    }


    private static class Edge {
        int vertex;
        int weight; //누적가중치

        Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }

}

 

 

최근에도 그러고 있지만 앞으로 알고리즘은 나중에 복습해도 될만한 문제만 포스팅에 기록하려고합니다. 

이전에는 저만의 레퍼런스용으로 복습도 하기 위해서 기록했는데 지금 기본문제들은 충분히 쌓인 것 같습니다. 

 

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. ㅎㅎ