[BOJ] 16926. 배열돌리기1 - Simulation

제출일 : 2019-10-20

문제 풀이 시간 : 3H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/16926

Input

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

Output

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

Constraints

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 10^8

Solution & Inpression

시뮬레이션 문제

시뮬레이션은 어렵다.

문제에 주어진대로 천천히 따라 코딩을 하면 되지만 2차원 배열의 인덱스 조작이 햇갈린다..

Code

언어 : JAVA

메모리 : 105,112 kb

실행시간 : 1,464 ms

import java.util.Scanner;

public class Main {
    static int N, M, R, S;
    static int[][] matrix, copy;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt(); // 배열의 크기 N*M
        M = sc.nextInt();
        R = sc.nextInt(); // 회전 수 R

        // min(N, M) mod 2 = 0
        S = Math.min(N, M) / 2; // 1회전에서 돌려야하는 사각형의 개수

        matrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < R; i++) {
            spin();
        }

        print();
    }

    private static void print() {
        for (int[] is : matrix) {
            for (int i : is) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    static void spin() {
        for (int s = 0; s < S; s++) {
            int T = s;
            int B = N - 1 - s;
            int R = M - 1 - s;
            int L = s;

            int tmp = matrix[s][s];
            for (int i = L; i < R; i++)    matrix[T][i] = matrix[T][i + 1];
            for (int i = T; i < B; i++)    matrix[i][R] = matrix[i + 1][R];
            for (int i = R; i > L; i--)    matrix[B][i] = matrix[B][i - 1];
            for (int i = B; i > T; i--)    matrix[i][L] = matrix[i - 1][L];
            matrix[T + 1][L] = tmp;

        }
    }
}

[BOJ] 15685. 드래곤커브 - Simulation

제출일 : 2019-10-19

문제 풀이 시간 : 3H

난이도 : ★★★★

Problem

link : https://www.acmicpc.net/problem/15685

Input

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

Output

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

Example

input

3
3 3 0 1
4 2 1 3
4 2 2 1

output

4

Solution & Inpression

시뮬레이션 문제

시뮬레이션은 역시 어렵다.

90도 시계방향으로 회전하는 것을 벡터의 회전이라 생각했고

• x' = xcos(90)-ysin(90)
• y' = xsin(90)+ycos(90)

라는 공식에 의해 새로운 좌표는 x'=-y, y'=x가 된다.

또 문제를 풀때 기억해야 할 부분은 끝에 점이 붙는것과 붙은 선분은 시작점에서부터 먼점에 있는 선분부터 시작이라는것이다.

햇갈려....

Code

언어 : JAVA

메모리 : 14,984 kb

실행시간 : 124 ms

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N;
    static ArrayList<Dragon> list;
    static int[][] map = new int[101][101];

    static class Dragon {
        ArrayList<int[]> point;

        public Dragon(int[] p, int dir, int g) {
            this.point = new ArrayList<>();
            this.point.add(p);
            if (dir == 0)
                this.point.add(new int[] { p[0], p[1] + 1 });
            else if (dir == 1)
                this.point.add(new int[] { p[0] - 1, p[1] });
            else if (dir == 2)
                this.point.add(new int[] { p[0], p[1] - 1 });
            else
                this.point.add(new int[] { p[0] + 1, p[1] });
            while (g-- != 0) {
                spin();
            }
        }

        void spin() {

            // x' = xcos(90)-ysin(90)
            // y' = xsin(90)+ycos(90)

            // sin(90) = 1;
            // cos(90) = 0;

            // x' = -y
            // y' = x
            int size = point.size();
            for (int i = size - 1; i > 0; i--) {
                int[] cen = point.get(i - 1);
                int[] cur = point.get(i);
                int[] end = point.get(point.size() - 1);

                int tx = cur[0] - cen[0];
                int ty = cur[1] - cen[1];

                int nx = end[0] - ty;
                int ny = end[1] + tx;

                point.add(new int[] { nx, ny });
            }

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt(); // 드래곤 커브의 개수 N(1 ≤ N ≤ 20)
        list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int c = sc.nextInt();
            int r = sc.nextInt();
            list.add(new Dragon(new int[] { r, c }, sc.nextInt(), sc.nextInt()));
        }

        for (int i = 0; i < N; i++) {
            ArrayList<int[]> l = list.get(i).point;
            for (int j = 0; j < l.size(); j++) {
                map[l.get(j)[0]][l.get(j)[1]] = 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < 101; j++) {
                if (map[i][j] == 1)
                    if (check(i, j))
                        ans++;
            }
        }
        System.out.println(ans);
    }

    private static boolean check(int i, int j) {
        int[] dr = { 1, 0, 1 };
        int[] dc = { 0, 1, 1 };

        for (int k = 0; k < 3; k++) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (!range(r, c)) {
                return false;
            } else {
                if (map[r][c] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < 101 && 0 <= c && c < 101)
            return true;
        return false;
    }
}

[BOJ] 17143. 낚시왕 - Simulation

제출일 : 2019-10-18

문제 풀이 시간 : 4H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/17143

Input

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

Output

낚시왕이 잡은 상어 크기의 합을 출력한다.

Example

input

4 6 8
4 1 3 3 8
1 3 5 2 9
2 4 8 4 1
4 5 0 1 4
3 3 1 2 7
1 5 8 4 3
3 6 2 1 2
2 2 2 3 5

output

22

Solution & Inpression

시뮬레이션 문제

요즘 계속 DFS와 BFS를 응용한 문제들만 풀어서 시뮬레이션 문제가 다시 어렵게 느껴졌다.

최악의 경우 맵의 크기는 100x100이고 상어는 최대 100x100마리이고 모든 상어의 속력이 1000이라면

10,000,000,000번의 연산을 수행해야 한다고 생각을 했기 때문에 무식하게 상어를 움직이면 안된다고 생각을하여 위치와 속도와 방향을 계산하여 상어를 한번에 옮기고 싶어 오랫동안 고민했지만, 식이 세워지지 않았다.

나중에 다시 식을 세워 풀어봐야 겠다.

Code

언어 : JAVA

메모리 : 61,940 kb

실행시간 : 1,604 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    static int R, C, M;
    static int[][] map;
    static ArrayList<Shark> list;

    static class Shark {
        int r, c, speed, direction, size;

        public Shark(int r, int c, int speed, int direction, int size) {
            this.r = r;
            this.c = c;
            this.speed = speed;
            this.direction = direction;
            this.size = size;
        }

        void move() {
            if (direction == 1) { // 위쪽 방향
                int dir = -1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    r += dir;
                    if (r == 0 || r == R + 1) {
                        dir *= -1;
                        r += dir*2;
                    }
                }
                if (dir == 1) // 바뀐 방향이 아래쪽이면
                    direction = 2;
            } else if (direction == 2) {
                int dir = 1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    r += dir;
                    if (r == 0 || r == R + 1) {
                        dir *= -1;
                        r += dir*2;
                    }
                }
                if (dir == -1) // 바뀐 방향이 위쪽이면
                    direction = 1;
            } else if (direction == 3) { // 오른쪽
                int dir = 1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    c += dir;
                    if (c == 0 || c == C + 1) {
                        dir *= -1;
                        c += dir*2;
                    }
                }
                if (dir == -1) // 바뀐 방향이 왼쪽이면
                    direction = 4;
            } else { // 왼쪽
                int dir = -1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    c += dir;
                    if (c == 0 || c == C + 1) {
                        dir *= -1;
                        c += dir*2;
                    }
                }
                if (dir == 1) // 바뀐 방향이 오른쪽이면
                    direction = 3;
            }

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();

        M = sc.nextInt();
        list = new ArrayList<>();
        map = new int[R][C];
        for (int k = 0; k < M; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            list.add(new Shark(i, j, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        int ans = 0;
        for (int king = 1; king <= C; king++) {
            sort();
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j).c == king) {
                    ans += list.get(j).size;
                    list.remove(j); // 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다
                    break;
                }
            }
            for (int j = 0; j < list.size(); j++) {
                list.get(j).move();
            }
        }
        System.out.println(ans);
    }

    static void sort() {
        Collections.sort(list, new Comparator<Shark>() {
            public int compare(Shark o1, Shark o2) {
                if (o1.r - o2.r != 0) {
                    return o1.r - o2.r;
                } else {
                    if (o1.c - o2.c != 0)
                        return o1.c - o2.c;
                    else {
                        return o2.size - o1.size;
                    }
                }
            }
        });

        for (int i = 0; i < list.size() - 1; i++) {
            Shark s1 = list.get(i);
            Shark s2 = list.get(i + 1);
            if (s1.r == s2.r && s1.c == s2.c) {// 위치가 같으면
                //System.out.println("EAT");
                list.remove(i + 1);
                i--;
            }
        }
    }
}

[BOJ] 17142. 연구소3 - Combination & BFS

제출일 : 2019-10-17

문제 풀이 시간 : 2H

난이도 : ★★★★

Problem

link : https://www.acmicpc.net/problem/17142

Input

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

Output

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

Example

input

7 3
2 0 2 0 1 1 0
0 0 1 0 1 2 0
0 1 1 2 1 0 0
2 1 0 0 0 0 2
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 2 0 2

output

4

Solution & Inpression

시뮬레이션 문제

연구소 1을 푼지 하루도 되지 않았을때 풀기 시작한 문제 이번에도 역시 모든경우의 조합을 구해 완전탐색을 진행하여 문제를 풀었다.

처음 모든 테스트케이스를 맞추고 제출하였을때 채점이 99%에서 틀렸습니다 메시지가 나왔다.

문제를 천천히 읽었을때 비활성화된 바이러스는 고려하지 않고 빈공간만 탐색하면 된다고 생각을 했고 그렇게 구현을 하였다. 테스트케이스는 맞지만 문제에는 맞지않는 구현이었고 친구의 도움으로 반례를 찾아 풀수 있었다.

찾은 반례는

1x3의 배열에 왼쪽부터 빈공간, 비활성화 된 바이러스, 활성화된 바이러스 순으로 들어있다면 결과는 2가 나와야하지만 -1이 나오게 된다. 따라서 2를 무시하면 안된다는 결론에 이르렀고 2도 역시 탐색의 기준으로 주어줬다.

2를 고려했을때도, 비활성화된 바이러스, 빈공간, 활성화된 바이러스 순이라면 결과는 1이나와야하지만 결과값은 2로 나오게 되었다.

이런 문제를 찾은 뒤에는 0과 2일때 탐색을 하며 0일때만 시간을 갱신해주는 방법으로 문제를 해결했다.

Code

언어 : JAVA

메모리 : 51,032 kb

실행시간 : 376 ms

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[][] map, copyMap;
    static ArrayList<int[]> virus;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][N];
        copyMap = new int[N][N];
        virus = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 2)
                    virus.add(new int[] { i, j });
            }
        }
        ans = Integer.MAX_VALUE;
        visit = new boolean[virus.size()];
        combination(virus.size(), M, 0, 0);

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }// end of main

    static void combination(int n, int r, int start, int depth) {
        if (r == depth) {

            BFS();
            return;
        }
        for (int i = start; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                combination(n, r, i, depth + 1);
                visit[i] = false;
            }
        }
    }

    private static void BFS() {

        for (int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();
        }

        int[] dr = { 1, -1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };
        int time = 0;
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < visit.length; i++) {
            if (visit[i]) {
                copyMap[virus.get(i)[0]][virus.get(i)[1]] = 3;
                q.offer(new int[] { virus.get(i)[0], virus.get(i)[1], 0 });
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int k = 0; k < 4; k++) {
                int r = cur[0] + dr[k];
                int c = cur[1] + dc[k];
                // 범위 내이고 0과 2일때만 BFS
                if (range(r, c)) {
                    if (copyMap[r][c] == 0) {
                        if (time < cur[2] + 1)
                            time = cur[2] + 1;
                        copyMap[r][c] = 3;
                        q.offer(new int[] { r, c, cur[2] + 1 });
                    } else if (copyMap[r][c] == 2) {
                        copyMap[r][c] = 3;
                        q.offer(new int[] { r, c, cur[2] + 1 });
                    }
                }
            }

        } // end of while

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (copyMap[i][j] == 0)
                    return;
            }
        }

        if (ans > time)
            ans = time;

    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }

}// end of Class

[BOJ] 14502. 연구소 - Combination&BFS

제출일 : 2019-10-16

문제 풀이 시간 : 1H 30M

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/14502

Input

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

Output

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

Example

input

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

output

27

Solution & Inpression

시뮬레이션 문제

처음 문제를 읽었을때 BFS를 이용하여 바이러스를 퍼트리는 문제임은 쉽게 이해할 수있다.

하지만 벽을 세울때 어떻게 새워야 하는지 오랫동안 고민 하다. 방법을 모르겠어서 계산기를 키고 최악의 경우를 계산하기 시작했다

최악의 경우 8x8 크기의 2차원 배열에 바이러스가 2개만 존재하며 벽은 하나도 없을때 벽을 세울수 있는 경우의 수라고 생각을 했고 이 경우는 $_{62}C_3=37,820$으로 나오기때문에 조합을 이용하여 완전 탐색을 하면 되겠다라고 생각을 정리하고 문제를 풀기 시작했다.

문제를 풀며 직면했던 문제는

1. 오랜만에 구현해본 조합
2. 2차원 배열의 깊은 복사

정도로 쉽게 해결할 수 있었다.

Code

언어 : JAVA

메모리 : 134,316 kb

실행시간 : 548 ms

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, max;
    static int[][] map, copyMap;
    static boolean[] visit;
    static ArrayList<int[]> virus, wall;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        virus = new ArrayList<>();
        wall = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 0) {
                    wall.add(new int[] { i, j });
                } else if (map[i][j] == 2) {
                    virus.add(new int[] { i, j });
                }
            }
        }
        max = Integer.MIN_VALUE;
        visit = new boolean[wall.size()];
        copyMap = new int[N][M];
        combination(wall.size(), 3, 0, 0);
        System.out.println(max);
    }

    static void combination(int n, int r, int depth, int start) {
        if (r == depth) {
            for(int i = 0; i<N; i++)
                copyMap[i] = map[i].clone();
            for (int i = 0; i < n; i++) {
                if (visit[i]) {
                    copyMap[wall.get(i)[0]][wall.get(i)[1]] = 1;
                }
            }
            BFS();
            return;
        }
        for (int i = start; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                combination(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

    private static void BFS() {
        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, 1, -1 };
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < virus.size(); i++) {
            q.offer(virus.get(i));
        }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int r = cur[0] + dr[k];
                int c = cur[1] + dc[k];

                if (range(r, c)) { // 범위 안
                    if (copyMap[r][c] == 0) {
                        copyMap[r][c] = 2;
                        q.offer(new int[] { r, c });
                    }
                }
            }
        } // end of while
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copyMap[i][j] == 0)
                    count++;
            }
        }
        if (max < count)
            max = count;
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < M)
            return true;
        return false;
    }

}

[BOJ] 16234. 인구이동 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

link : https://www.acmicpc.net/problem/16234

Input

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

Output

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

Example

input

2 20 50
50 30
20 40

output

1

Solution & Inpression

시뮬레이션 문제

처음에 문제를 풀땐 국경을 공유할수 있는나라를 다 검사한뒤 connect 배열을 이용하여 체크를 한뒤 연합을 구성할때 DFS를 이용하여 라벨링을 했었다. 이렇게 문제를 푼다면 테스트 케이스는 맞게 되지만

2 10 50
10 100
50 50

이러한 경우에 2개의 연합이 구성되지만 1개의 연합으로 인식하게 되어 문제를 틀리게 된다.

따라서 아래와 같은 방법으로 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 37,292 kb

실행시간 : 444 ms

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, L, R, num;
    static int[][] map, connect;

    static int[] dr = { 1, -1, 0, 0 };
    static int[] dc = { 0, 0, 1, -1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
        N = sc.nextInt();
        // 두 나라의 인구 차이가 L명 이상, R명 이하라면
        L = sc.nextInt();
        R = sc.nextInt();
        map = new int[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                map[i][j] = sc.nextInt();

        int ans = 0;
        while (true) {

            connect = new int[N][N];
            num = 1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (connect[i][j] == 0) {
                        if (DFS(i, j, num))
                            num++;
                    }
                }
            }

            if (num == 1) {
                System.out.println(ans);
                return;
            }

            int[] cnts = new int[num];
            int[] sums = new int[num];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    sums[connect[i][j]] += map[i][j];
                    cnts[connect[i][j]]++;
                }
            }

            for (int i = 1; i < num; i++)
                sums[i] /= cnts[i];

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if (connect[i][j] != 0)
                        map[i][j] = sums[connect[i][j]];

            ans++;
        }
    }

    private static boolean DFS(int i, int j, int num) {
        boolean flag = false;
        for (int k = 0; k < 4; k++) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (isRange(r, c) && connect[r][c] == 0) {
                int dif = Math.abs(map[i][j] - map[r][c]);
                if (L <= dif && dif <= R) {
                    connect[r][c] = num;
                    DFS(r, c, num);
                    flag = true;
                }
            }
        }
        if (flag) {
            connect[i][j] = num;
            return true;
        }
        return false;
    }

    private static boolean isRange(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }

}

[BOJ] 16236. 아기상어 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/16236

Input

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

Output

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

Example

input

6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

output

60

Solution & Inpression

시뮬레이션 문제

문제에서 시키는데로 차근차근 풀게되면 어려움이 없는 문제

BFS를 이용하여 먹을수 있는 물고기를 ArrayList에 저장하고, 어떤 물고기를 먼저 먹을지 문제에 주어졌고 ArrayList의 정렬조건을 문제에서 주어진대로 주고 가장 첫번째 인덱스의 물고기를 잡아먹었다.

Code

언어 : JAVA

메모리 : 21,144 kb

실행시간 : 192 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, time;
    static int[][] map;
    static int[] dr = { 1, -1, 0, 0 };
    static int[] dc = { 0, 0, 1, -1 };
    static Shark s;

    static class Shark {
        int size, r, c, count;

        @Override
        public String toString() {
            return "Shark [size=" + size + ", r=" + r + ", c=" + c + ", count=" + count + "]";
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // 0: 빈 칸
        // 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
        // 9: 아기 상어의 위치
        map = new int[N][N];
        s = new Shark();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int tmp = sc.nextInt();
                map[i][j] = tmp;
                if (tmp == 9) {
                    s.r = i;
                    s.c = j;
                    s.size = 2;
                    s.count = 0;
                }
            }
        }
        time = 0;
        while (move(s)) {
        }
        System.out.println(time);

    }

    private static boolean move(Shark s) {

        boolean[][] visit = new boolean[N][N];
        Queue<int[]> q = new LinkedList<>();
        ArrayList<int[]> list = new ArrayList<>();
        q.offer(new int[] { s.r, s.c, 0 });
        visit[s.r][s.c] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int r = cur[0] + dr[k];
                int c = cur[1] + dc[k];

                if (range(r, c) && !visit[r][c]) {
                    visit[r][c] = true;
                    if (map[r][c] > s.size)// 지나가지도 먹지도 못함
                        continue;
                    else if (map[r][c] == s.size || map[r][c] == 0) // 지나갈순 있지만 먹진 못함.
                        q.offer(new int[] { r, c, cur[2] + 1 });
                    else {
                        list.add(new int[] { r, c, cur[2] + 1 });
                    }
                }
            }
        } // end of while

        if (list.isEmpty())
            return false;
        else {
            Collections.sort(list, new Comparator<int[]>() {
                public int compare(int[] o1, int[] o2) {
                    int r = o1[2] - o2[2]; // 거리순으로
                    if (r == 0) {// 위쪽 우선순위
                        int r2 = o1[0] - o2[0];
                        if (r2 == 0) {// 왼쪽 우선순위
                            return o1[1] - o2[1];
                        } else
                            return r2;
                    } else
                        return r;
                }
            });

            eat(list.get(0));
            return true;
        }

    }

    private static void eat(int[] fish) {
        time += fish[2];
        map[s.r][s.c] = 0;
        s.r = fish[0];
        s.c = fish[1];
        s.count++;
        if (s.count == s.size) {
            s.size++;
            s.count = 0;
        }
        map[fish[0]][fish[1]] = 9;
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}

[BOJ] 16235. 나무 재테크 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

link : https://www.acmicpc.net/problem/16235

Input

첫째 줄에 K년이 지난 후 살아남은 나무의 수를 출력한다.

Output

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

Constraint

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
• 입력으로 주어지는 나무의 위치는 모두 서로 다름

Example

input

5 2 4
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3
3 2 3

output

13

Solution & Inpression

시뮬레이션 문제

문제에서 시키는데로 차근차근 풀게되면 어려움이 없는 문제지만

1*1 한칸에 여러 나무가 심어질수 있기때문에 자료구조를 어떻게 해야할지 고민을 하게 만든 문제였다.

처음 내가 생각한 자료구조는 ArrayList<Integer>[][]로 2차원 배열의 원소값이 ArrayList로 이루어진 자료구조를 선언하고 사용하려 했다.

하지만 다른 2차원 배열과 다르게 사용을 할 수 가 없었고, 모든 나무를 하나의 PriorityQueue에 모든 정보를 담아 문제를 풀었다.

Code

언어 : JAVA

메모리 : 165,300 kb

실행시간 : 1,532 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static int N, M, K;
    static int[][] robot, land;

    static PriorityQueue<Tree> tree;

    static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };

    static class Tree implements Comparable<Tree> {
        int r, c, age;

        public Tree(int r, int c, int age) {
            this.r = r;
            this.c = c;
            this.age = age;
        }

        public int compareTo(Tree t) {
            return this.age > t.age ? 1 : -1;
        }

        public String toString() {
            return "(r=" + r + ", c=" + c + ", age=" + age + ")";
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt() + 1; // 땅의 크기 1base
        int M = sc.nextInt(); // 나무 수
        int K = sc.nextInt(); // 년 수
        robot = new int[N][N];
        land = new int[N][N];

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                robot[i][j] = sc.nextInt();// 로봇이 추가하는 양분
                land[i][j] = 5; // 초기 양분
            }
        }

        tree = new PriorityQueue<>();
        for (int i = 0; i < M; i++) {
            tree.offer(new Tree(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
        ArrayList<Tree> dead = new ArrayList<>();
        ArrayList<Tree> alive = new ArrayList<>();
        for (int year = 0; year < K; year++) {
            // 봄
            while (!tree.isEmpty()) {
                Tree t = tree.poll();
                if (land[t.r][t.c] < t.age) {// 죽는다
                    dead.add(t);
                } else {
                    land[t.r][t.c] -= t.age; // 양분을 먹고
                    t.age++; // 한살도 먹고
                    alive.add(t);
                }
            }

            // 여름
            for (int i = 0; i < dead.size(); i++) {
                Tree t = dead.get(i);
                // 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다
                land[t.r][t.c] += t.age / 2;
            }
            dead.clear();

            // 가을
            for (int i = 0; i < alive.size(); i++) {
                Tree t = alive.get(i);
                if (t.age % 5 != 0) {// 번식하지 못하는 나무
                    tree.offer(t);
                } else {
                    tree.offer(t);
                    for (int k = 0; k < 8; k++) {
                        int r = t.r + dr[k];
                        int c = t.c + dc[k];
                        if (1 <= r && r < N && 1 <= c && c < N) {
                            Tree nt = new Tree(r, c, 1);
                            //System.out.println("    " + nt);
                            tree.offer(nt);
                        }
                    }
                }
            }
            alive.clear();

            // 겨울
            for (int i = 1; i < N; i++) {
                for (int j = 1; j < N; j++) {
                    land[i][j] += robot[i][j];
                }
            }
        }
        System.out.println(tree.size());

    }
}