[백준] 2536번 : 버스 갈아타기 - 자바(JAVA)

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

2536번: 버스 갈아타기

 

문제 해석

2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있습니다.

아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예시입니다.

가로 7 세로 6

이 도로망을 운행하는 버스들이 k개 존재하며 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 수직선 상의 두 교차점 사이 선분을 왕복 운행합니다.

 

즉, 가로 또는 세로로만 움직인다

 

출발점 교차점과 목적지 교차점이 주어질 때 (출발지와 목적지는 다름) , 출발지에서 목적지로 버스만을 이용해서 가려고 한다.

 

이때 버스의 최수 수를 구하는 프로그램을 작성하세요

 

예를 들어,  8대의 버스가 다음과 같이 운행한다고 하자.

• 1번 버스: (2, 1) - (2, 2)
• 2번 버스: (1, 1) - (5, 1)
• 3번 버스: (3, 2) - (6, 2)
• 4번 버스: (5, 6) - (5, 1)
• 5번 버스: (1, 5) - (7, 5)
• 6번 버스: (7, 3) - (7, 6)  
• 7번 버스: (2, 1) - (2, 6) 
• 8번 버스: (3, 5) - (6, 5)

출발지는 (2,1)이며 목적지는 (7,4)입니다.

 

방법 1

처음에 2번 버스를 타고 (5,1)에 내린다

4번 버스를 타고 (5,5)에서 내린다.

5번 버스를 탄 후 (7,5)에서 내린다.

6번 버스를 타서 목적지인 (7,4)에 내린다.

 

이용한 버스 수 4개

 

방법 2

7번 버스를 타고 (2,5)에 내린다.

5번 버스를 타고 (7,5)에 내린다.

6번 버스를 타고 (7,4)에 내린다

 

이용한 버스 수 3개

 

문제 풀이 전 설계

버스의 수는 1~5000이며 목적지로 가는 방법은 한 가지 이상 존재합니다.

 

모든 경우의 수를 찾으며 가능한 경로를 탐색하는 것은 시간 초과가 예상됩니다.

 

파라메틱 서치를 활용하여 버스의 정답 범위를 1~5000으로 놓고 이분 탐색으로 출발지에서 도착지로 가는 길의 최소 값을 탐색합니다.

 

이때 BFS,DFS를 활용하여 이미 한번 탑승했던 버스를 제외하고 갈 수 있는 노선들을 가보면서  정답 범위를 벗어나면 continue 합니다.

 

예를 들어 1~5000에서 시작하면 middle값은 2500부터 시작할 것이며 2500개를 초과하는 버스를 사용해야 하는 경로들은 더 이상 탐색하지 않습니다.

 

문제 풀이하면서

파라메틱 서치보다는 그냥 BFS로 탐색하면 해결되는 문제였습니다.

 

1. 시작점이 버스노선에 포함되는 경우 q에 넣기

2. q가 빌 때까지 반복

3. 모든 버스를 확인하며 방문되지 않았으며 교차되는 경우 q에 넣기

4. 도착지에 포함되면 종료

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2536_버스갈아타기 {
    static int m,n,k, sx,sy,dx,dy;
    static int idx[], startX[], startY[];
    static int endX[], endY[];
    static Queue<Integer> qu = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());
        idx = new int[k];
        startX = new int[k];
        startY = new int[k];
        endX = new int[k];
        endY = new int[k];

        int[] busCount = new int[k];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine()," ");
            idx[i]=Integer.parseInt(st.nextToken());
            startX[i]=Integer.parseInt(st.nextToken());
            startY[i]=Integer.parseInt(st.nextToken());
            endX[i]=Integer.parseInt(st.nextToken());
            endY[i]=Integer.parseInt(st.nextToken());
            if(startX[i]>endX[i]) {//x가 같음. 세로줄
                int temp = startX[i];
                startX[i] = endX[i];
                endX[i] = temp;
            }
            if(startY[i]>endY[i]){//y가 같음. 가로줄
                int temp = startY[i];
                startY[i] = endY[i];
                endY[i] = temp;
            }
        }

        st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken());
        sy = Integer.parseInt(st.nextToken());
        dx = Integer.parseInt(st.nextToken());
        dy = Integer.parseInt(st.nextToken());

        //시작점이 버스노선에 포함되는 경우
        for (int i = 0; i < k; i++) {
            if(IsIncluded(sx,sy,i)) {
                busCount[i]=1;
                qu.offer(i);
            }
        }

        int busNo = 0;
        while(!qu.isEmpty()) {
            busNo = qu.poll();

            //도착지에 포함되면 종료
            if(IsIncluded(dx, dy, busNo)) {
                System.out.println(busCount[busNo]);
                break;
            }
            for (int i = 0; i < k; i++) {
                //방문되지 않았으며 교차되는경우
                if(busCount[i]==0 && isCross(busNo, i)) {
                    busCount[i] = busCount[busNo]+1;
                    qu.offer(i);
                }
            }
        }
    }//end main..

    private static boolean isCross(int a, int b) {
        if(startX[a] == endX[a]) {// ㅣ
            if(startX[b] == endX[b]) {// ㅣ
                return startX[a]==startX[b] && !((startY[a]>endY[b]) || (startY[b]>endY[a]));
            }else {//ㅡ
                return startX[a]>=startX[b] && startX[a]<=endX[b] && startY[b]>=startY[a] && startY[b]<=endY[a];
            }
        }else {// ㅡ
            if(startX[b] == endX[b]) {// ㅣ
                return startX[b]>=startX[a] && startX[b]<=endX[a] && startY[a]>=startY[b] &&startY[a]<=endY[b];
            }else {  // ㅡ
                return startY[a]==startY[b] && !((startX[a]>endX[b]) || (startX[b]>endX[a]));

            }
        }
    }

    private static boolean IsIncluded(int x, int y, int idx) {
        return startX[idx]<=x && x<=endX[idx] && startY[idx]<=y && y<=endY[idx];
    }

}