[BOJ] 5884. Three Lines (bruteforce)

#. Problem

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

* 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

- 최대 세 개의 감시 카메라로 N(1 ≤ N ≤ 50,000) 마리 소를 감시
- 카메라는 한 수직/수평선을 감시

 

최대 세 개의 감시 카메라로 모든 소를 감시하기 위해, 
감시 카메라는 수직 1대, 수평 2대가 설치되거나 / 수직 2대, 수평 1대가 설치되어야 한다.
(수직 혹은 수평 한 축에 3대를 설치해야만 하는 경우는 없음) 

[ 동작 ]

1. 모든 소의 좌표 저장
2. X 좌표 기준 정렬
3. 모든 소의 수평선에 카메라 설치
     - y 좌표 기준으로 소가 있는 모든 수평선에 카메라를 설치하면서 해당 수평선에 몇 마리의 소가 있는지 카운트
4. x 좌표에 중복이 있고 y 좌표에 중복이 없는 수직선에 카메라 설치
     - x 좌표 기준으로 소가 있는 모든 수직선을 확인하면서 해당 수직선에 카메라를 설치할지 체크
5. 최대 세 개의 감시 카메라로 모든 소를 감시할 수 있는지 확인
6. x, y 좌표를 바꿔서 2번부터 다시 수행

#. Code

import java.io.*;
import java.util.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
 
    static class Point implements Comparable<Point> {
        int x, y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public void switching() {
            int tmp = this.x;
            this.x = this.y;
            this.y = tmp;
        }
 
        /**
         * order by x asc, y asc
         */
        @Override
        public int compareTo(Point p) {
            if (this.x == p.x) {
                return Integer.compare(this.y, p.y);
            } else {
                return Integer.compare(this.x, p.x);
            }
        }
    }
    static int N, cntCamera = 0;
    static Map<Integer, Integer> cntCowByLine;
    static List<Point> cowsList;
    void solve() {
        
        N = in.nextInt();
        cowsList = new ArrayList<>();
        // 1. 모든 소의 좌표 저장
        for (int i = 0; i < N; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            cowsList.add(new Point(x, y));
        }
        
        // 2. X 좌표 기준 정렬
        cowsList.sort(null);
        // 3. 모든 소의 수평선에 카메라 설치
        setCameraOnY();
        // 4. x 좌표에 중복이 있고 y 좌표에 중복이 없는 수직선에 카메라 설치
        setCameraOnX();
        
        // 5. 최대 세 개의 감시 카메라로 모든 소를 감시할 수 있는지 확인
        if (isPossible()) {
            out.println(1);
            return;
        }
        
        // 6. x, y 좌표 바꿔서 다시 수행
        cntCamera = 0;
        for (Point p : cowsList) p.switching();
        
        cowsList.sort(null);
        setCameraOnY();
        setCameraOnX();
        
        if (isPossible()) {
            out.println(1);
        } else {
            out.println(0);
        }
    }
    
    private void setCameraOnY() {
        
        cntCowByLine = new HashMap<>();
        
        // y 좌표 기준으로 소가 있는 모든 수평선에 카메라를 설치하면서 해당 수평선에 몇 마리의 소가 있는지 카운트
        for (Point p : cowsList) {
            if (cntCowByLine.get(p.y) == null) {
                cntCowByLine.put(p.y, 1);
                cntCamera++;
            } else {
                cntCowByLine.put(p.y, cntCowByLine.get(p.y) + 1);
            }
        }
    }
    
    private void setCameraOnX() {
        
        int xLine = -1;
        
        // x 좌표 기준으로 소가 있는 모든 수직선을 확인하면서 해당 수직선에 카메라를 설치할지 체크
        for (Point p : cowsList) {
            // 해당 점의 수평선에 다른 소가 있는 경우 패스. 
            if (cntCowByLine.get(p.y) > 1) continue;
            
            // 해당 점의 수평선에 다른 소가 없는 경우
            // 이전에 설치한 수직선과 같은 라인에 있다면 수평선에 설치된 카메라를 없애주자
            if (xLine == p.x) {
                cntCamera--;
            } else {
                // 수직선에 새로 카메라를 설치할 경우
                xLine = p.x;
            }
        }
    }
    
    private Boolean isPossible() {
        // 모든 소를 감시하기 위해 카메라가 3대 넘게 설치될 경우 실패
        if (cntCamera > 3) {
            return false;
        } else {
            return true;
        }
    }
 
    /********************************** Input function **********************************/
    
    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());
        }
    }
}