[알고리즘풀이]백준 1753 : 최단경로 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1753번 최단경로를 풀었습니다. 이를 정리해보고자 합니다.

1753번: 최단경로

 

본문

1) 문제

2) 과정

이번 문제는 푸는데 2시간 정도 걸렸습니다. 1916번 문제를 풀고나니까 쉽게 풀 수 있던 문제였어요 :)

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

 

 

제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다.

0) s->f로의 비용에 맞춰 ArrayList배열에 연결정보를 넣는다.
1) 배열을 만들고, 시작점 위치를 넣어준다.
2) 방문여부와 이어지는 노드가 있는지 체크하고 통과가되면 새 비용과 원래비용을 비교한다.
3) 새 비용이 원래비용보다 작다면 새비용을 dp와 q에 값을 넣는다.

 

이 문제를 해결하면서 visited의 위치를 설정하는게 중요하단걸 알게되었는데요. 1916까지는 visited의 위치에 대해 깊게 고민하지 않았는데 이번 문제로 그 이유를 알게되었습니다.

그 이유가 궁금하다면 ? => 맨 아래 깃헙링크에 방문하시면 맨 위 상단에 에러로그로 따로 모아뒀으니 이를 확인하시면 됩니다!

이번문제도 코테의 기본 구성인 Input,Logic,Output으로 문제 풀이를 나눠볼게요 :) 처음이신 분들은 Input, Logic, Output으로 풀이를 나눠두시면 수정하시거나 이해하는데 도움이 되니 한번 해보셔도 좋을 것 같아요!!

문제에 대한 설명들은 주석으로 충분히 설명한 것 같아서 따로 달지는 않겠습니다!!!

 

2-1) Input

    public static void main(String[] args) throws IOException{
        // Input
        MyIO io = new MyIO();
        io.readLine();
        int n = io.nextInt(); // 노드의 수
        int e = io.nextInt(); // 간선의 수
        int sp = io.readIntLine(); // 시작점

        ArrayList<int[]>[] edgeArr = new ArrayList[n+1];
        for(int i=0;i<e;i++){
            io.readLine();
            int s = io.nextInt(); // 첫 위치
            int f = io.nextInt(); // 끝 위치
            int cost = io.nextInt(); // 이동 비용
            // s->f로 갈때 비용이 cost인걸 맞춰 edgeArr에 값을 넣어줌.
            if(edgeArr[s]==null) edgeArr[s]=new ArrayList<>();
            edgeArr[s].add(new int[]{f,cost});
        }
    }    
    // 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());}
    }

Input은 대부분의 변수들을 생성하고 initialize하는 내용들입니다 ! 아래 설명을 읽으시다가 모르시는 변수가 있다면 주석을 통해 확인하세요!

 

2-2) Logic & Output

        // Logic
        // initialize arrays
        Queue<int[]> q = new PriorityQueue<>((o1,o2)->Integer.compare(o1[1],o2[1])); // 탐색할때 사용할 큐
        int[] dp = new int[n+1]; // 각 노드까지의 최단거리를 저장할 배열
        Arrays.fill(dp, Integer.MAX_VALUE); // 초기값 셋팅
        boolean[] visited = new boolean[n+1]; // 방문여부 체크
        // set first value
        q.add(new int[]{sp,0});
        dp[sp] = 0;
        // start searching
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int pos = cur[0]; 
            int cost = cur[1];
            // 방문여부 체크
            if(visited[pos]) continue;
            visited[pos] = true;
            // 이어지는 노드가 없다면 넘어가도록 체크
            if(edgeArr[pos]==null) continue;
            for(int[] next : edgeArr[pos]){
                int nextPos = next[0];
                int nextCost = next[1];
                // 새 비용과 원래 있던 최단비용을 비교하여 새 비용이 최단이면 이를 큐와 dp에 넣는다.
                if(cost+nextCost < dp[nextPos]){
                    q.add(new int[]{nextPos, cost+nextCost});
                    dp[nextPos] = cost+nextCost;
                }
            }
        }

        // Output
        for(int i=1;i<=n;i++) System.out.println(dp[i]==Integer.MAX_VALUE?"INF":dp[i]);

 

 

3) 전체코드

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

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

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

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