[백준 - 1613][GOLD 3][해설 X] - 역사 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/1613

 

문제

---

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

 

입력

---

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

 

출력

---

첫째 줄에 정답을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int inf = Integer.MAX_VALUE/2; //연결되지 않은 것을 표현
                      			//이때 inf끼리 더해져 int형을 벗어나는 문제를 피하기 위해 절반 값을 사용한다.

        List<Integer> graph[] = new ArrayList[n+1];
        int[][] distance = new int[n+1][n+1];
		
        //그래프 초기화
        for(int i=0;i<=n;i++){
            graph[i] = new ArrayList<>();
            Arrays.fill(distance[i],inf);
        }
		
        //그래프 생성
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());

            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());

            distance[before][after] = 1;

            graph[before].add(after);
        }
		
        //플로이드 워셜을 이용해 모든 경로간 거리를 구한다
        for(int mid=1;mid<=n;mid++){
            for(int end=1;end<=n;end++){
                for(int start=1;start<=n;start++){
                    if(distance[start][end] > distance[start][mid] + distance[mid][end]){
                        distance[start][end] = distance[start][mid] + distance[mid][end];
                    }
                }
            }
        }

        int s = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int i=0;i<s;i++){
            st = new StringTokenizer(br.readLine());

            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());
		
        	//before -> after의 경로가 존재하면 정방향이다.
            if(distance[before][after] != inf){
                sb.append(-1);
            }
            //정방향은 경로가 없지만 역방향이 있다면 역방향이다.
            else if(distance[after][before] != inf){
                sb.append(1);
            }
            //아무것도 없다면 경로가 없다.
            else{
                sb.append(0);
            }

            sb.append("\n");
        }

        sb.deleteCharAt(sb.length()-1);

        System.out.println(sb);
    }
}

 

 

실행 결과

---

 

팁

---

• 경로가 존재한다 -> 부모-자식관계를 빠르게 생각할 수 있는 것이 핵심