[BOJ] 소가 길을 건너간 이유 Series.java

소가 길을 건너간 이유 6 을 풀고,

문제가 너무 재미있어서

나도 소가 길을 건너간 이유를 연구해보려고 한다.

일명.. Cow R&D..

...

#. Series 1

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

* The copyright in this matter is in BOJ

#. Solve

 

Cow R&D 에 온 걸 환영하는 문제다.

먼저 소가 길을 건너는 것을 관찰하면서

처음 확인하는 소라면 위치를 체크해두고

이미 확인했던 소라면 길을 건넜는지 확인해주자.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class BOJ14467 {       static int N, observe[];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  N = Integer.parseInt(br.readLine());         observe = new int[N];         Arrays.fill(observe, -1);                  int cnt = 0;         for (int i = 0; i < N; i++) {                      st = new StringTokenizer(br.readLine());                          int c = Integer.parseInt(st.nextToken()) - 1;             int p = Integer.parseInt(st.nextToken());                          // 처음 확인하는 Cow             if(observe[c] == -1) observe[c] = p;             // 이미 확인했던 Cow라면 길을 건넜는지 확인             else if(observe[c] != p) {                 observe[c] = p;                 cnt++;             }         }                  System.out.println(cnt);     }   }   Colored by Color Scripter

cs

---

#. Series 2

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

* The copyright in this matter is in BOJ

#. Solve

약간 그리디스러운 문제다.

O(52 * 52 * 26) 로 풀었다.

효율적이지 않은 방법일 수도 있다..

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;   public class BOj14468 {       public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         String input = br.readLine();                  boolean[] check = new boolean[26];         int[] alpa;         int cnt = 0;         for (int d = 0; d < input.length(); d++) {                          int now = input.charAt(d) - 'A';             // 이미 확인한 소라면 pass             if(check[now]) continue;                          // 확인한 소 체크             check[now] = true;             // 소의 출입 상태 확인             alpa = new int[26];             alpa[now]++;                          // 해당 소가 나가는 점이 나올 때까지             for (int nd = d + 1; nd < input.length(); nd++) {                                  int next = input.charAt(nd) - 'A';                 // 등장하는 소 확인                 alpa[next]++;                   // 해당 소가 나가는 점이 나왔을 때,                  if(next == now) {                     // 아직 나오지 않은 소 확인                     for (int i = 0; i < 26; i++)                          if(!check[i] && alpa[i] == 1) cnt++;                                          break;                 }             }         }                   System.out.println(cnt);     }   }   Colored by Color Scripter

cs

---

#. Series 3

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

* The copyright in this matter is in BOJ

#. Solve

소가 도착한 시간순으로 정렬하고

모든 소가 도착하고 검문받는데까지 걸리는 시간을 누적해주면 된다.

신경써야할 부분은

바로 검문을 받을 수 있는데, 소가 늦게 도착한 경우?!

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ14469 {
 
    static int N;
    static Cow[] cows;
    static class Cow implements Comparable<Cow> {
        int arrive, check;
 
        public Cow(int arrive, int check) {
            super();
            this.arrive = arrive;
            this.check = check;
        }
 
        @Override
        public int compareTo(Cow o) {
            return Integer.compare(this.arrive, o.arrive);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        cows = new Cow[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            cows[i] = new Cow(Integer.parseInt(st.nextToken()), 
                    Integer.parseInt(st.nextToken()));
        }
        
        // 도착한 시간순으로 정렬
        Arrays.sort(cows);
        
        // 첫 번째 소가 도착한 시간
        int time = cows[0].arrive;
        for (int i = 0; i < N; i++) {
            // 바로 검문을 받을 수 있는데, 소가 늦게 도착할 경우
            if(time < cows[i].arrive) time = cows[i].arrive;
            
            time += cows[i].check;
        }
        
        System.out.println(time);
    }
 
}
 

---

#. Series 4

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

* The copyright in this matter is in BOJ

#. Solve

따로 포스팅-> 링크 클릭!

---

#. Series 5

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

* The copyright in this matter is in BOJ

#. Solve

따로 포스팅-> 링크 클릭!

---

#. Series 6

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

* The copyright in this matter is in BOJ

#. Solve

따로 포스팅했음!-> 링크 클릭!

#. Code

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ14466 {
 
    static int N, K, R;
    static boolean[][] visited;
    static Point[] cows;
    static ArrayList<Point>[][] bridges;
    static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); // 크기
        K = Integer.parseInt(st.nextToken()); // 소 몇 마리?
        R = Integer.parseInt(st.nextToken()); // 길
 
        cows = new Point[K];
        bridges = new ArrayList[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                bridges[i][j] = new ArrayList<>();
            }
        }
        
        // 다리 정보 저장
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int d = Integer.parseInt(st.nextToken()) - 1;
            
            bridges[a][b].add(new Point(c, d));
            bridges[c][d].add(new Point(a, b));
        }
        
        // 소 위치 저장
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            
            cows[i] = new Point(a, b);
        }
        
        System.out.println(go());
    }
 
    private static int go() {
        
        int cnt = 0;
        
        // 소 한 마리씩 길을 건너지 않고 이동해보자.
        for (int c = 0; c < K; c++) {
            visited = new boolean[N][N];
            move(cows[c].x, cows[c].y);
             
            for (int nc = c; nc < K; nc++) {
                Point cow = cows[nc];
                // 이 소가 방문하지 않은 곳에 소가 있다면
                // 길을 건너지 않으면 만나지 못 하는 쌍이 된다.
                if(!visited[cow.x][cow.y]) cnt++;
            }
 
        }
                
        return cnt;
    }
 
    private static void move(int x, int y) {
        
        visited[x][y] = true;
        
        for (int d = 0; d < 4; d++) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            // 범위
            if(xx < 0 || xx >= N || yy < 0 || yy >= N) continue;
            // 이미 방문
            if(visited[xx][yy]) continue;
            // 길을 건너야 한다면
            if(bridges[x][y].contains(new Point(xx, yy))) continue;
            
            move(xx, yy);
        }
        
    }
 
}
 

---

#. Series 7

* The copyright in this matter is in BOJ

#. Solve

#. Code