[알고리즘풀이]백준 1240 : 노드 사이의 거리 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1240번 노드 사이의 거리를 풀었습니다. 이를 정리해보고자 합니다.

 

본문

1) 문제

2) 과정

이번 문제는 무난무난하게 1시간 정도 걸려서 풀었습니다.

DFS도 해보고 BFS도 해봤는데 DFS로 했을 때 메모리 초과가 발생해서 BFS로 작성을 완료했던 문제입니다.

BFS도 처음에 멍청하게 방문했던 모든 경로의 가중치를 더해버려서 이상한 값이 나왔었어요 ㅋㅋㅋㅋㅋㅋ 그래도 해결해서 잘 마쳤습니다.

 

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

0. n+1사이즈의 array안에 ArrayList를 넣고, ArrayList안에는 int[]가 있는 구조를 준비한다.

1. 값을 입력받을 때 [노드번호]([연결된번호, 거리값])으로 값을 넣어준다.
2. 로직을통해 큐에 현재위치와 시작점에서의 거리를 넘겨주며 탐색을 진행한다.
3. ep(end point)에 도착하면 ans에 dist를 넣어주고 while문을 종료한다.
4. ans를 출력하고 m번동안 2~4를 반복한 뒤 종료한다.

 

모든 내용을 main에 적긴 했지만 Input, Logic, Outpu에 맞춰 설명을 해볼게요! (이렇게 3가지로 나눠서 작성하면 나중에 부분이 바뀌어도 더 편하게 바꿀 수 있어서 선호하는 편이예요!)

2-1) Input

        // Input
        // read n,m value
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        // read connection
        ArrayList<int[]>[] orgArr = new ArrayList[n+1];
        for(int i=1;i<n;i++){
            st= new StringTokenizer(br.readLine());
            int one = Integer.parseInt(st.nextToken());
            int oth = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            // make connection
            if(orgArr[one]==null) orgArr[one] = new ArrayList<>();
            orgArr[one].add(new int[]{oth,val}); // {연결된번호, 거리}
            if(orgArr[oth]==null) orgArr[oth] = new ArrayList<>();
            orgArr[oth].add(new int[]{one,val}); // {연결된번호, 거리}
        }

입력은 크게 2개의 부분으로 나눠져요. n과 m을 읽는 부분, 간선의 정보를 읽어 연결을 만드는 부분으로 나눠집니다.

저는 orgArr에 int[]을 사용해 연결된번호와 거리를 담아 사용했어요. 그렇게 연결된 두 노드모두에 각각의 연결정보를 넣어줬습니다.

 

2-2) Logic & Output

        // Logic
        for(int i=0;i<m;i++){
            // read the two points whose distance what I want to know
            st= new StringTokenizer(br.readLine());
            int sp = Integer.parseInt(st.nextToken());
            int ep = Integer.parseInt(st.nextToken());
            // make visited array - 방문여부 체크를 위해 visited를 만듦.(+시작점을 넣어줌)
            boolean[] visited = new boolean[n+1];
            visited[sp] = true; 
            // make q - 현재 위치와 시작점(sp)에서 해당 지점까지의 거리를 담아 state를 전달하기 위해 만듦(+시작점을 넣어줌)
            Queue<int[]> q = new ArrayDeque<>();
            q.add(new int[]{sp,0});
            // BFS
            int ans = 0;
            while(!q.isEmpty()){
                // read a state
                int[] cur = q.poll();
                // end condition - ep에 도착하면 dist를 ans에 저장하고 종료
                if(cur[0]==ep) {
                    ans=cur[1];
                    break; 
                }
                // 현재 위치의 자식을 탐색
                for(int[] contSet : orgArr[cur[0]]){
                    int cont = contSet[0];
                    int d = contSet[1];
                    // check visited
                    if(visited[cont]) continue;
                    visited[cont] = true;
                    // add state for the next
                    q.add(new int[]{cont,cur[1]+d});
                }
            }

            // Output
            System.out.println(ans);

Output이 너무 짧아서 Logic과 함께 작성하려고 합니다!

 

Logic을 세부적으로 나누면

1. 두 점을 입력받는다.

2. 시작점(sp)의 방문여부 체크 및 큐에 넣어 탐색할 준비를 합니다.

    - 큐는 현재 점의 위치와 시작점부터 현재점까지의 거리를 전달합니다.

3. BFS탐색을 합니다

    - 도착점(ep)에 도착할 때까지 현재점의 자식을 계속해서 방문하며 큐에 담아 탐색합니다.

    - 도착점에 도착하면 ans에 그간의 거리를 담고 while문을 빠져나옵니다.

4. ans(sp~ep의거리)를 출력합니다.

 

3) 전체코드

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

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

 

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ1240.java

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