[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());

    }
}

[BOJ] 14891. 톱니바퀴 - Simulation

제출일 : 2019-10-14

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

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

Input

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

Output

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

Example

input

10101111
01111101
11001110
00000010
2
3 -1
1 1

output

7

Solution & Inpression

Code

언어 : JAVA

메모리 : 14,536 kb

실행시간 : 124 ms

import java.util.*;

public class Main {
    static int[][] wheels;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        wheels = new int[5][8];
        for (int i = 1; i <= 4; i++) {
            String str = sc.next();
            for (int j = 0; j < 8; j++) {
                if (str.charAt(j) == '1')
                    wheels[i][j] = 1; // S극
                else
                    wheels[i][j] = 0; // N극
            }
        }

        int K = sc.nextInt(); // 회전 횟수 K;
        for (int i = 0; i < K; i++) {
            // 톱니바퀴 번호, 방향(1:시계 -1:반시계)
            isspin(sc.nextInt(), sc.nextInt());
        }

        System.out.println(1 * wheels[1][0] 
                         + 2 * wheels[2][0] 
                         + 4 * wheels[3][0] 
                         + 8 * wheels[4][0]);

        sc.close();
    }

    //좌우에 톱니를 회전할 수 있는지 확인.
    private static void isspin(int num, int dir) { 
        //회전이 가능한 톱니번호와 뱡향을 저장
        ArrayList<int[]> list = new ArrayList<>(); 

        list.add(new int[] { num, dir });

        int flag = dir;
        int temp = num;
        int right = wheels[num][2]; //현재 바퀴의 오른쪽값.
        while (temp + 1 <=4) { // 오른쪽에 바퀴가 존재한다면
            if (right != wheels[temp + 1][6]) {//회전이 가능한지 
                temp++;
                flag *= -1;
                right = wheels[temp][2]; 
                list.add(new int[] { temp, flag });
            }
            else
                break;
        }

        flag = dir;
        temp = num;
        int left = wheels[num][6]; //현재 바퀴의 왼쪽값.
        while (temp - 1 >=1) { // 왼쪽에 바퀴가 존재한다면
            if (left != wheels[temp - 1][2]) { //회전이 가능한지
                temp--;
                flag *= -1; //반대방향
                left = wheels[temp][6]; 
                list.add(new int[] { temp, flag });
            }
            else
                break;
        }
        for (int i = 0; i < list.size(); i++) {
            spin(list.get(i)[0], list.get(i)[1]);
        }
    }

    private static void spin(int num, int dir) {
        int[] temp = wheels[num].clone(); // 복사

        if (dir == 1) {// 시계방향이면 >> 오른쪽으로 한칸씩
            for (int i = 1; i < 8; i++) {
                wheels[num][i] = temp[i - 1];
            }
            wheels[num][0] = temp[7];
        } else {// 반시계방향이면 >> 왼쪽으로 한칸씩
            for (int i = 1; i < 8; i++) {
                wheels[num][i - 1] = temp[i];
            }
            wheels[num][7] = temp[0];
        }
    }
}

[BOJ] 14890. 경사로 - Simulation

제출일 : 2019-10-14

문제 풀이 시간 : 2H

난이도 : ★★★★☆

Problem

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

Input

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

Output

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

Example

input

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

output

3

Solution & Inpression

해결하지 못한 문제.

Code

언어 : JAVA

메모리 : 25,868 kb

실행시간 : 240 ms

import java.util.*;

public class Main {
    static int[][] wheels;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        wheels = new int[5][8];
        for (int import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int N, L;
    static int[][] map;
    static boolean[][] visitRow, visitCol;

    static ArrayList<int[]> v;

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

        N = sc.nextInt();
        L = 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;
        int j = 0;// 끝에 도착시 j로 체크
        for (int i = 0; i < N; i++) {
            int cnt = 1;
            for (j = 0; j < N-1; j++) { //가로: 좌->우
                     if(map[i][j]  ==map[i][j+1])            cnt++; //평지
                else if(map[i][j]+1==map[i][j+1] && cnt>= L) cnt=1; //오르막
                else if(map[i][j]-1==map[i][j+1] && cnt>= 0) cnt=-L+1; //내리막
                else break;
            }
            if(j==N-1 && cnt>= 0) ans++; //끝에 도착

            cnt=1;
            for (j = 0; j < N-1; j++) { //세로: 상->하
                     if(map[j][i]  ==map[j+1][i])            cnt++; //평지
                else if(map[j][i]+1==map[j+1][i] && cnt>= L) cnt=1; //오르막
                else if(map[j][i]-1==map[j+1][i] && cnt>= 0) cnt=-L+1; //내리막
                else break;
            }
            if(j==N-1 && cnt>= 0) ans++; //끝에 도착

        }

        System.out.println(ans);
    }
}

[BOJ] 14889. 스타트와 링크- Permutation

제출일 : 2019-10-14

문제 풀이 시간 : 40M

난이도 : ★★

Problem

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

Input

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

Output

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

Example

input

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

output

0

Solution & Inpression

N개중 N/2개를 선택하여 2개의 그룹으로 나눈뒤 각각의 그래프의 가중치를 더해 최솟값을 찾는 문제. [BOJ]게리멘더링을 풀기전에 풀어보았더라면 게리멘더링을 더 쉽게 풀었을것 같다.

Code

언어 : JAVA

메모리 : 17,560kb

실행시간 : 336 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[][] matrix;
    static int[] visit;
    static int min;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        min = Integer.MAX_VALUE;
        visit = new int[N];
        solve(N, N / 2, 0, 0);
        System.out.println(min);

    }

    static void solve(int n, int r, int depth, int start) {
        if(depth!=0&&visit[0]==0)
            return;
        if (depth == r) {
            int team1 = 0, team2 = 0;
            //System.out.println(Arrays.toString(visit));
            for (int i = 0; i < n; i++) {
                if (visit[i] == 1)
                    for (int j = 0; j < n; j++) {
                        if (i != j && visit[j] == 1)
                            team1 += matrix[i][j];
                    }
                else
                    for (int j = 0; j < n; j++) {
                        if (i != j && visit[j] == 0)
                            team2 += matrix[i][j];
                    }
            }
            int res = Math.abs(team1 - team2);
            if (res < min)
                min = res;
            return;
        }

        for (int i = start; i < n; i++) {
            if (visit[i] == 0) {
                visit[i] = 1;
                solve(n, r, depth + 1, i);
                visit[i] = 0;
            }
        }
    }
}