[백준] 22948 원 이동하기2

1. 문제

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

22948번: 원 이동하기 2

2. 접근방법

아이디어만 떠올리면 어렵지 않은 문제였다.

 

각 원에 접점이 있지 않기 때문에

포함관계가 분명하게 있고 각 원은 모두 하나의 직속 부모만을 가지게 된다.

즉, 트리 형태로 나타 낼 수 있다.

 

트리로 바꾼 후에는 bfs를 통해 시작점에서 도착점까지 가장 짧은 노드를 찾으면 된다.

 

트리로 바꾸는 작업은 괄호를 처리하는 것과 비슷한 개념으로

각 원의 x축에 닿는 왼쪽 오른쪽 점을 우선순위 큐에 넣어

왼쪽 점을 만나면 괄호가 열린것 오른쪽 점을 만나면 괄호가 닫힌 것으로 생각하고

직속 부모와 자식을 연결리스트로 나타내주면 된다.

 

3. 자바 코드

package backjoon;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class P22948원이동하기2 {
    static ArrayList<Integer> [] nodeList;
    static class node{
        int node;
        int cnt;
        String allNode;

        public node(int node,int cnt ,String allNode) {
            this.node = node;
            this.cnt = cnt;
            this.allNode = allNode;
        }
    }
    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());
        nodeList = new ArrayList[N+1];
        for(int i = 0 ; i <=N ; i++)nodeList[i] = new ArrayList<>();
        PriorityQueue<Point> pq = new PriorityQueue<>((o1, o2) -> { //x = 좌표, y= 번호
            return o1.x - o2.x;
        });
        pq.add(new Point(-10000000,0));
        pq.add(new Point(10000000,0));
        for(int i = 0 ; i < N ; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            pq.add(new Point(x-r,k));
            pq.add(new Point(x+r,k));
        }
        makeTree(pq,-1);

        st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken());
        int to = Integer.parseInt(st.nextToken());

        boolean visit[] = new boolean[N+1];
        Queue<node> que = new LinkedList<>();
        visit[from] = true;
        que.add(new node(from,1,""+from));
        while(!que.isEmpty()){
            node now = que.poll();
            if(now.node == to){
                System.out.println(now.cnt);
                System.out.println(now.allNode);
                return;
            }
            for(int next : nodeList[now.node]){
                if(visit[next])
                    continue;
                visit[next]= true;
                que.add(new node(next, now.cnt+1,now.allNode+" "+next));
            }
        }
    }

    static void makeTree(PriorityQueue<Point> pq,int parents ){
        Point now = pq.poll();
        if(parents != -1) {
            nodeList[parents].add(now.y);
            nodeList[now.y].add(parents);
        }
        while(now.y != pq.peek().y){
            makeTree(pq,now.y);
        }
        pq.poll();
    }
}

4. 마치며

두개의 개념이 섞여서 재밌는 문제였다.