[백준, Java] 16965번, 구간과 쿼리(BFS)

문제 링크

16965번: 구간과 쿼리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

1. 쿼리는 2가지 종류가 존재하며, 문제에서 정의하고 있습니다.

2. 각 구간이 이동할 수 있는 조건은  (x2 < x1 < y2) 또는 (x2 < y1 < y2)을 만족해야 합니다.

3. 모든 쿼리에 따른 결과를 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 쿼리에 맞게 구간을 추가하거나 BFS을 이용해서 이동할 수 있는지 확인합니다.

 

3. 2 a b에 대한 쿼리 결과를 출력합니다.

 

 

쿼리 진행하기

 

1 x y

 

해당 구간을 List<>에 저장합니다.

 

2 a b

 

BFS을 진행하여 a번째 구간이 b번째 구간으로 이동할 수 있는지 확인합니다.

 

※예제입력 과정을 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 5

 

쿼리

 

1 1 5

1 5 11

2 1 2

1 2 9

2 1 2

 

 

2. 쿼리에 맞게 구간을 추가하거나 BFS을 이용해서 이동할 수 있는지 확인합니다.

 

1 1 5

 

구간 더하기!

 

현재 구간 : { 1, 5 }

 

 

 

 

 

1 5 11

 

구간 더하기!

 

현재 구간 : { 1, 5 }, { 5, 11 }

 

 

 

 

2 1 2

 

이동할 수 있는지 BFS 진행!

 

 

1번째 구간 : { 1, 5 }

 

2번째 구간 : { 5, 11 }

 

1번째 구간에서 이동할 수 있는 구간은 아무것도 존재하지 않기 때문에 2번째 구간에 도달하지 못합니다.

 

→ 0

 

 

1 2 9

 

구간 더하기!

 

현재 구간 : { 1, 5 }, { 5, 11 }, { 2, 9 }

 

 

2 1 2

 

이동할 수 있는지 BFS 진행!

 

1번째 구간 : { 1, 5 }

 

2번째 구간 : { 5, 11 }

 

1번째 구간에서 이동할 수 있는 구간은 { 2, 9 }

 

2 < 5(y) < 9 : 성립

 

{ 2, 9 }에서 이동할 수 있는 구간은 { 5, 11 }

 

5 < 9(y) < 11 : 성립  

 

목적지 도착!!

 

→ 1

 

3. 2 a b에 대한 쿼리 결과를 출력합니다.

 

쿼리를 통해 얻은 결과

 

0

 

1

 

결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 쿼리의 입력값을 띄어쓰기 기준 저장합니다.
• 1 x y인 쿼리는 구간을 List<>에 추가합니다.
• 2 a b인 쿼리는 search함수를 통해서 이동할 수 있는지 확인합니다.
• 쿼리에 대한 결과들을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 BFS을 통해서 a → b로 이동할 수 있는지 확인합니다.
• check함수는 x₂ < n < y₂ 조건에 만족하는지 확인합니다.

결과코드

import java.io.*;
import java.util.*;


public class Main {
    //구간 정보 클래스
    static class Info{
        int x, y;
        Info(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    //구간 저장 리스트
    static List<Info> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //0번째 구간 아무것도 아닌 더미 값 설정
        list.add(new Info(0, 0));
        //쿼리 진행
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int command = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 1 x y : 구간 더하기
            if(command == 1) {
                list.add(new Info(a, b));
            }else{	// 2 a b : BFS을 통해 이동할 수 있는지 확인
                if(search(a, b, N)){		//이동할 수 있을 때
                    bw.write("1\n");
                }else{		//이동할 수 없을 때
                    bw.write("0\n");
                }
            }
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통해 a → b 이동할 수 있는지 확인하는 함수
    static boolean search(int start, int end, int N){
        Queue<Info> q = new ArrayDeque<>();
        boolean[] visited = new boolean[N+1];
        //방문한 구간 확인 배열
        visited[start] = true;
        //시작 구간 a을 Queue 삽입
        q.add(list.get(start));
        //BFS 진행
        while(!q.isEmpty()){
            Info cur = q.poll();
            //목적 구간 b에 도착했을 때
            if(cur.x == list.get(end).x && cur.y == list.get(end).y){
                return true;
            }
            //이동할 수 있는 구간 탐색
            for(int i=1;i<list.size();i++){
                Info info = list.get(i);
                //조건에 만족해서 이동할 수 있는 구간일 때
                if(!visited[i] && (check(info, cur.x) || check(info, cur.y))){
                    visited[i] = true;
                    q.add(info);
                }
            }
        }
        return false;	// a에서 b로 이동하지 못할 때
    }
    //이동 조건 처리하는 함수
    static boolean check(Info nxt, int val){
        //x2 < n < y2 조건 처리
        if(val > nxt.x && val < nxt.y){
            return true;
        }
        return false;
    }
}