[SWEA] 5431. 민석이의 과제 체크하기 D3

제출일 : 2019-07-16

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl3rWKDBYDFAXm

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 수강생의 수를 나타내는 정수 N(2≤N≤100)과 과제를 제출한 사람의 수를 나타내는 정수 K(1≤K≤N)가 공백으로 구분되어 주어진다.

두 번째 줄에는 과제를 제출한 사람의 번호 K개가 공백으로 구분되어 주어진다. 번호는 1이상 N이하의 정수이며 같은 번호가 두 번 이상 주어지는 경우는 없다.

Output

각 테스트 케이스마다 과제를 제출하지 않은 사람의 번호를 오름차순으로 출력한다.

Example

input

2
5 3
2 5 3
7 2
4 6

output

#1 1 4
#2 1 2 3 5 7

Code

언어 : JAVA

메모리 : 56,744 kb

실행시간 : 363 ms

import java.util.*;
import java.io.*;

public class Solution{
    public static void main(String args[]) throws Exception {
        //System.setIn(new FileInputStream("res/input_d3_5431.txt"));
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();

        for (int i = 0; i < N; i++) {

            int students = s.nextInt();
            int submit = s.nextInt();

            int[] mem = new int[students];

            for (int j = 0; j < submit; j++) {
                int temp = s.nextInt();
                mem[temp - 1]++;
            }
            System.out.print("#" + (i + 1) + " ");

            for (int j = 0; j < students; j++) {
                if (mem[j] == 0)
                    System.out.print((j + 1) + " ");
            }
            System.out.println();

        }

        s.close(); // Scanner close
    }
}

[SWEA] 1208. Flatten D3

제출일 : 2019-07-16

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh

Input

총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다. 그리고 다음 줄에 각 상자의 높이값이 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 최고점과 최저점의 높이 차를 출력한다.

Example

input

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

output

#1 13
#2 32
...

Code

언어 : JAVA

메모리 : 23,404 kb

실행시간 : 178 ms

import java.util.*;
import java.io.*;

public class Solution{
    public static void main(String args[]) throws Exception {

        Scanner s = new Scanner(System.in);
        for (int tc = 1; tc <= 10; tc++) {
            int Dump = s.nextInt(); // 834

            int[] box = new int[100];

            for (int i = 0; i < 100; i++) {
                box[i] = s.nextInt();
            } 
            Arrays.sort(box);

            int head = 0;
            int tail = 99;
            while (true) {

                box[head]++;
                box[tail]--;
                Dump--;
                Arrays.sort(box);
                if (Dump == 0)
                    break;
            }

            System.out.println("#" + tc + " " + (box[99] - box[0]));
        }
        s.close(); // Scanner close
    }
}

[SWEA] 1204. 최빈수 구하기 D2

제출일 : 2019-07-16

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13zo1KAAACFAYh

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호가 주어지고 그 다음 줄부터는 점수가 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

Example

input

10
1
41 85 72 38 80 69 65 68 96 22 49 67 51 61 63 87 66 24 80 83 71 60 64 52 90 60 49 31 23 99 94 11 25 24 51 15 13 39 67 97 19 76 12 33 99 18 92 35 74 0 95 71 39 33 39 32 37 45 57 71 95 5 71 24 86 8 51 54 74 24 75 70 33 63 29 99 58 94 52 13 35 99 46 57 71 23 17 3 94 48 77 18 83 11 83 25 59 62 2 78 86 7 94 65 80 32 39 84 60 65 72 61 58 84 8 72 12 19 47 49 49 59 71 52 34 22 21 20 92 33 80 39 74 9 28 97 100 93 29 25 4 66 79 81 98 21 91 62 82 4 59 100 34 1 51 80 92 69 77 39 38 97 51 34 35 19 22 1 67 9 90 31 82 11 51 84 78 70 74 42 100 88 53 80 57 62 32 51 48 63 92 46 4 61 31 98 69 52 88 20 68 41 48 79 97 98 56 44 73 3 63 100 87 87 41 79 64 83 63 1 21 72 24 9 75 51 25 53 77 0 52 30 96 93 32 89 70 89 55 71 79 40 10 64 80 30 19 62 67 98 42 8 32 57 27 22 1 38 89 52 74 43 8 2 65 82 20 67 22 43 22 95 16 48 25 6 75 86 96 3 85 43 69 93 4 61 53 81 43 84 20 15 34 22 35 26 28 33 67 19 79 19 45 8 13 51 0 86 68 18 47 82 3 16 80 0 18 39 22 5 26 65 70 21 92 66 65 14 6 46 46 21 32 80 35 86 6 67 29 42 71 14 77 55 3 1 14 38 71 82 41 65 12 5 77 3 67 22 59 40 81 48 63 63 25 45 32 78 83 26 96 18 99 45 56 31 30 45 47 80 1 7 81 18 1 90 15 71 22 69 44 18 31 60 16 93 13 17 44 97 98 51 46 42 22 47 72 97 24 52 55 59 25 100 28 5 14 76 32 41 97 61 32 20 0 2 8 41 52 77 35 22 98 78 92 68 29 82 33 28 16 5 9 21 13 26 39 59 69 10 42 4 13 80 34 42 100 44 32 70 15 32 8 83 10 23 73 8 53 7 21 10 52 14 82 28 24 33 94 59 4 17 73 53 85 31 100 74 74 12 72 38 34 14 22 53 0 30 95 3 52 79 41 36 81 25 24 67 48 95 44 7 96 77 90 48 92 45 78 93 95 38 71 4 83 79 64 89 0 76 81 34 66 1 13 58 4 40 5 24 17 6 65 13 13 76 3 20 8 36 12 60 37 42 53 87 10 65 42 25 47 41 33 71 69 94 24 12 92 11 71 3 82 91 90 20 95 44 76 60 34 95 49 40 89 4 45 27 9 34 82 59 2 20 68 22 29 10 1 23 19 47 16 76 47 49 90 94 10 18 55 69 14 26 59 77 73 8 21 72 1 74 76 51 94 44 24 98 71 77 59 9 12 49 38 72 22 55 35 61 16 48 41 21 67 74 92 4 7 85 34 92 39 96 42 26 1 1 4 64 33 96 62 23 67 76 26 47 32 73 82 30 14 61 21 92 40 4 2 38 76 64 8 14 3 49 71 31 38 86 98 17 15 98 32 55 69 46 61 3 44 67 50 44 76 0 45 23 25 11 82 99 11 39 50 40 21 52 17 60 44 90 44 6 16 38 3 41 43 56 26 24 0 9 90 36 50 13 42 88 87 66 32 28 73 94 52 11 35 47 9 87 37 57 15 56 38 95 6 43 23 30 84 39 88 69 5 34 81 93 86 2 77 10 28 30 97 68 14 12 88 1 100 35 73 30 2 43 11 41 58 82 6 84 71 16 18 67 41 100 92 78 57 7 35 69 56 76 13 93 26 26 38 21 96 7 88 2 60 17 54 95 26 2 0 21 87 11 96 36 83 88 31 24 24 62 14 88 84 39 22 17 84 96 1 78 91 53 9 35 75 87 100 33 80 42 7 20 50 65 81 92 14 45 96 34 6 20 86 51 4 19 70 91 13 0 42 70 43 15 47 14 96 72 41 91 11 72 7 92 12 16 51 13 86 40 50 43 55 26 7 1 70 18 71 99 49 55 94 78 40 59 20 96 34 6 28 85 42 70 62 63 32 34 97 80 49 47 50 73 85 63 20 29 0 19 91 84 58 55 33 4 68 55 12 38 49 9 13 99 4 35 26 5 42 29 98 20 95 77 36 63 41 42 45 81 40 53 60 5 55 9 13 34 6 52 28 35 33 29 21 67 57 61 21 41 95 54 50 19 81 75 67 73 77 47 40 83 16 28
.......

output

#1 71
#2 76
.......

Code

언어 : JAVA

메모리 : 36,640 kb

실행시간 : 204 ms

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;

public class Solution{
    public static void main(String args[]) throws Exception {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();


        for (int i = 1; i <= N; i++) {
            int num = s.nextInt();
            int[] array = new int[1000]; 

            for (int j = 0; j < 1000; j++) { 
                array[j] = s.nextInt();
            }


            int[] countarray = new int[101];

            for (int j = 0; j < 1000; j++) {
                countarray[array[j]]++; 
            }

            int result = 0;
            int temp = 0;

            for (int j = 100; j >= 0; j--) {
                if (result < countarray[j]) {
                    result = countarray[j];
                    temp = j;
                }
            }

            System.out.println("#" + num + " " + temp);

        } 

    }

}

[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;
    }
}