[알고리즘풀이]백준 1916 : 최소비용 구하기 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1916번 최소비용 구하기를 풀었습니다. 이를 정리해보고자 합니다.

1916번: 최소비용 구하기

 

본문

1) 문제

2) 과정

처음 풀었던 shortest Path(최단거리) 문제라서 꽤나 오랜 시간... 5시간 조금 넘게 걸렸습니다... 분명 거의 다 되는데 왜 안될까 하며 삽질하는 시간이 길었어요... 이 문제는 노드에는 특별한 조건이나 문제가 없고 간선의 계산이 중점인 문제이기 때문에 노드 마다의 무언갈 만들기보단(노드를 담은 배열) 간선의 정보를 담는 노드와노드간의 값을 담은 배열이 필요하다는 생각으로 접근했습니다.

 

제가 문제를 풀며 사용했던 아이디어는 shotestPath를 구할때 대표적으로 사용하는 알고리즘인 dijkstra 알고리즘과 별 차이없이 구성했습니다.

0) edgeArr에 시작점에서 갈 수 있는 다음위치와 그 비용을 Node로 묶어 담아둔다.
1) 방문여부를 체크하며 sp(첫 시작위치)에서부터 큐를 이용해 탐색을 시작한다.
2) 탐색을 할때 다음위치에 미리 저장된 비용이 새롭게 이동했을때의 비용보다 큰지 확인하여 크다면 새 비용으로 갱신 및 큐에 추가를 반복한다.
3) 탐색을 마친 뒤 minCostArr(최소비용을 담아내는 배열, dp와 같음)의 ep(마지막 종료지점)을 출력한다.

 

 

이 문제를 풀면서도 꽤 많은 메모리초과와 시간초과를 겪었는데요... 이 과정이 궁금하시다면 맨아래있는 깃헙링크를 통해 확인하시기 바랍니다 😉

 

문제풀이는 Input,Logic,Output으로 나눠 보여드릴게요 :) 또한 설명은 주석으로 충분히 설명한 것 같아서 따로 달지 않겠습니다.

 

2-0) Node

    // Inner Class - save pos and cost and allows comparisons to be made.
    private static class Node implements Comparable<Node>{
        // Variable
        int pos;
        int cost;
        // Constructor
        public Node(int next, int cost){
            this.pos = next;
            this.cost = cost;
        }
        // Method
        @Override
        public int compareTo(Node o) {return this.cost - o.cost;}
    }

이번 문제를 풀면서 위치와 비용을 담고자 사용한 내부 클래스입니다. 앞으로 계속 나오니 먼저 확인하고 넘어가시면 좋을 것 같아 0번으로 보여드려요 !

 

2-1) Input

    public static void main(String[] args) throws IOException{
        // Input
        MyIO io = new MyIO();
        int n=io.readIntLine(); // 정류장의 총 개수
        int m=io.readIntLine(); // 버스노선의 총 개수

        List<Node>[] edgeArr = new ArrayList[n+1]; // 간선 연결 정보
        for(int i=0;i<m;i++){
            io.readLine();
            int a = io.nextInt(); // 출발지점(sNode)
            int b = io.nextInt(); // 도착지점(eNode)
            int c = io.nextInt(); // 버스비(cost)

            if(edgeArr[a]==null) edgeArr[a] = new ArrayList<>(); 
            edgeArr[a].add(new Node(b,c)); // 0처리하기
        }

        io.readLine();
        int sp = io.nextInt(); // 시작 위치(start position)
        int ep = io.nextInt(); // 종료 위치(end position)
    }
 
    
    // Inner Class - Read & Write values
    private static class MyIO{
        // Variable
        BufferedReader br;
        StringTokenizer st;
        // Constuctor
        public MyIO(){br = new BufferedReader(new InputStreamReader(System.in));} 
        // Method - for input
        public int readIntLine() throws IOException { readLine(); return nextInt();}
        public void readLine() throws IOException { st = new StringTokenizer(br.readLine());}
        public int nextInt(){ return Integer.parseInt(st.nextToken());}
    }

 

2-2) Logic & Output

        // Logic
        Queue<Node> q = new PriorityQueue<>(); // 위치와 이동하는데 걸린 비용을 저장
        q.add(new Node(sp,0)); // 시작점과 시작비용(0)을 담음

        boolean[] visited = new boolean[n+1]; // 방문여부를 판단하기 위함.

        int[] minCostArr = new int[n+1]; // [시작점][도착점] 의 최소비용을 담음
        Arrays.fill(minCostArr,Integer.MAX_VALUE); // 가장큰값으로 초기화
        minCostArr[sp] = 0; // 시작점의 비용은 0으로 셋팅

        while(!q.isEmpty()){
            Node cur = q.poll();
            // 방문여부 체크
            if(visited[cur.pos]) continue;
            visited[cur.pos] = true;
            // 다음 노선이 없는 경우 체크
            if(edgeArr[cur.pos]==null) continue;
            for(Node next : edgeArr[cur.pos]){
                // 다음정류장으로 갔을때의 총 비용 계산
                int nextCost = cur.cost + next.cost;
                // 다음위치의 최소비용과 nextCost를 비교
                if(minCostArr[next.pos]>nextCost){
                    // for next (nextCost로 다음위치의 최소비용 변경 및 큐에 추가)
                    minCostArr[next.pos] = nextCost;
                    q.add(new Node(next.pos,nextCost));
                }
            }
        }
        // Output
        System.out.println(minCostArr[ep]);

 

 

3) 전체코드

그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/shortest_path/BOJ1916.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비