[BOJ] 20652. Stuck in a Rut (simulation)

#. Problem

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

* The copyright in this matter is in acmicpc

 

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

소 1 <= N <= 50

* 소 일부는 북쪽, 일부는 동쪽으로 향한다.
* 소가 동시에 같은 셀로 오는 경우 셀 공유
* x 좌표는 고유하다.

ㅇ매시간, 모든 소의 동작
     - 현재 셀에 있는 풀을 이미 다른 소가 먹었을 경우 중지
     - 현재 셀의 풀을 모두 먹고 한 셀 이동(자신의 진행 방향)

ㅇ결과
     - 각 소가 먹는 풀의 양

 

//

 

동쪽을 향하는 소와 북쪽을 향하는 소가 중 한 마리의 소가 멈출 수 있는 공간은

동쪽을 향하는 소 기준으로 3시~6시 구역이다.

 

동쪽을 향하는 소들을 기준으로 가장 밑에 위치한 (testcase 기준 10, 4) 소부터 북쪽을 향하는 소들과 비교해보면 된다.

즉, 동쪽을 향하는 소들 중 가장 밑에 위치한 소부터 자신을 기준으로 3시~6시 구역에 위치한 북쪽을 향하는 소들과 비교를 해보자.

 

말로는 설명하기가 너무나 어렵다..

역시 개발자는 코드로 설명하고 코드를 보고 이해하는 게 더 편한 듯하다..?

 

#. Code

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
 
    static class Point implements Comparable<Point>{
        int x, y, num; // x y 좌표, 소 번호
        char dir; // 방향
 
        public Point(int x, int y, int num, char dir) {
            this.x = x;
            this.y = y;
            this.num = num;
            this.dir = dir;
        }
 
        @Override
        public int compareTo(Point o) {
            if (o.dir == 'E') return Integer.compare(this.y, o.y); // 동향 소들은 y기준 오름차순
            else return Integer.compare(this.x, o.x); // 북향 소들은 x기준 오름차순
        }
    }
 
    static int N, a, b, moveCnt[];
    static boolean isStopped[];
    static ArrayList<Point> ECows, NCows;
    void solve() {
        N = in.nextInt();
        ECows = new ArrayList<>();
        NCows = new ArrayList<>();
        moveCnt = new int[N];
        isStopped = new boolean[N];
        for (int i = 0; i < N; i++) {
            char dir = in.nextToken().charAt(0);
            int x = in.nextInt();
            int y = in.nextInt();
            if(dir == 'E') ECows.add(new Point(x, y, i, dir));
            else NCows.add(new Point(x, y, i, dir));
        }
 
        Collections.sort(ECows);
        Collections.sort(NCows);
        
        // 동쪽 방향으로 가는 소들
        for (Point ep : ECows) {
            // 북쪽 방향으로 가는 소들
            for (Point np : NCows) { 
                // 동향 소 기준 3시~6시 구역 확인
                if (isStopped[np.num]) continue; // 해당 구역에 북향 소가 멈춘 상태라면 pass
                if (ep.x > np.x || ep.y < np.y) continue; // 해당 구역에 없는 소라면 pass
                
                if (np.x - ep.x > ep.y - np.y) {// 두 소의 x좌표 차이가 y좌표 차이보다 크다면 동향 소가 멈춤
                    isStopped[ep.num] = true;
                    moveCnt[np.num] =  ep.y - np.y; // 북향 소는 y좌표 차이만큼 이동
                    moveCnt[ep.num] =  np.x - ep.x - 1; // 동향 소는 x좌표 차이 - 1만큼 이동
                    break;
                } else if (np.x - ep.x < ep.y - np.y) {// y좌표의 차이가 x좌표의 차이보다 크다면 북쪽 방향 소가 충돌
                    isStopped[np.num] = true;
                    moveCnt[np.num] =  ep.y - np.y - 1; // 북향 소는 y좌표 - 1만큼 이동
                    moveCnt[ep.num] =  np.x - ep.x; // 동향 소는 x좌표 차이 만큼 이동
                } else {
                    //소가 동시에 같은 셀로 오는 경우 셀 공유 
                    moveCnt[np.num] =  ep.y - np.y;
                    moveCnt[ep.num] =  np.x - ep.x;
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            if(!isStopped[i]) out.println("Infinity"); // 멈추지 않은 소는 영원히 달린다..
            else out.println(moveCnt[i] + 1);
        }
    }
 
    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
 
        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
 
        long nextLong() {
            return Long.parseLong(nextToken());
        }
 
        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}