[SWEA] 2117. 홈 방범 서비스 - Simulation

제출일 : 2019-11-12

문제 풀이 시간 : 1H

난이도 : ★★

Problem

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

Constraints

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초

2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)

3. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.

4. 도시에는 최소 1개 이상의 집이 존재한다.

input

각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.

Output

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

출력해야 할 정답은 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,

Example

input

10
8 3
0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0
1 0 0 0 0 0 0 0
…

output

#1 5
…

Solution & Inpression

모의 SW 역량테스트문제 중 가장 쉬웠던 문제인것 같다.

핵심은 마름모를 만드는것.
$$
if ((Math.abs(i - r) + Math.abs(j - c)) <= k - 1)
$$

Code

언어 : JAVA

메모리 : 45,780 kb

실행시간 : 499 ms

import java.util.Scanner;

public class Solution {
    static int N, M;
    static int[][] map;
    static int max;

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

        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt(); // 도시 크기
            M = sc.nextInt(); // 하나의 집이 지불할 수 있는 비용

            map = new int[N][N];
            int c = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int tmp = sc.nextInt();
                    map[i][j] = tmp; // 집이면 1
                    if (tmp == 1) {
                        c++;
                    }
                }
            }

            max = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (c == max)
                        break;
                    solve(i, j);
                }
            }

            System.out.println("#" + tc + " " + max);
        }
        sc.close();
    }

    private static void solve(int r, int c) {
        for (int k = 1; k <= N + N; k++) {
            int cnt = 0;
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if ((Math.abs(i - r) + Math.abs(j - c)) <= k - 1)
                        if (map[i][j] == 1)
                            cnt++;

            int cost = k * k + (k - 1) * (k - 1);
            if (cost <= cnt * M)
                if (max < cnt)
                    max = cnt;
        }
    }

}

[BOJ] 1600. 말이 되고픈 원숭이 - BFS

제출일 : 2019-11-12

문제 풀이 시간 : 1H 30M

난이도 : ★★★

Problem

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

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.

근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.

이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.

Input

첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

Output

첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

Example

input

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

output

5

Solution & Inpression

삼성 SW 역량 테스트 기출 문제

문제를 읽고 BFS문제라는것은 쉽게 파악이 가능했고 움직이는 dr배열도 아래와 같이 하면 해결할 수 있을것 같았다.

위의 테스트 케이스의 정답은 5이지만 결과가 -1로 나오기에 방문처리를 입력받은 K+1만큼을 만들어 사용하여 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 118,864 kb

실행시간 : 932 ms

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

public class Main {
    static int K, H, W;
    static int[][] map;
    static boolean[][][] visit;

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

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

        K = sc.nextInt();
        W = sc.nextInt();
        H = sc.nextInt();

        map = new int[H][W];
        visit = new boolean[K + 1][H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        sc.close();

        if (!BFS(0, 0))
            System.out.println(-1);
    }

    private static boolean BFS(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        visit[K][i][j] = true;
        q.offer(new int[] { i, j, K, 0 });
        int k;
        while (!q.isEmpty()) {
            int[] cur = q.poll();

            if (cur[0] == H - 1 && cur[1] == W - 1) { // 도착
                System.out.println(cur[3]);
                return true;
            }

            if (cur[2] > 0) {
                k = 0; // 점프
            } else
                k = 8; // 한칸씩 움직이는것 부터

            for (; k < dr.length; k++) {
                int r = cur[0] + dr[k];
                int c = cur[1] + dc[k];
                if (isRange(r, c)) // 범위 안이고
                    if (map[r][c] == 0) // 장애물이 아닌경우에
                        if (k >= 8) { // 뛴경우가 아닐때
                            if (!visit[cur[2]][r][c]) {
                                visit[cur[2]][r][c] = true; // 방문해
                                q.offer(new int[] { r, c, cur[2], cur[3] + 1 }); // 기회는 그대로
                            }
                        } else {
                            if (!visit[cur[2] - 1][r][c]) {
                                visit[cur[2] - 1][r][c] = true; // 방문해
                                q.offer(new int[] { r, c, cur[2] - 1, cur[3] + 1 }); // 기회 -1
                            }
                        }
            }
        } // end of while
        return false;
    }

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

}

[BOJ] 17779. 게리맨더링2 - BF

제출일 : 2019-11-12

문제 풀이 시간 : 4H

난이도 : ★★★★☆

Problem

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

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

x = 2, y = 4, d1 = 2, d2 = 2	x = 2, y = 5, d1 = 3, d2 = 2	x = 4, y = 3, d1 = 1, d2 = 1

구역 (r, c)의 인구는 $A[r][c]$이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

Input

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 $A[r][c]$를 의미한다.

Output

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

Constraints

• 5 ≤ N ≤ 20
• 1 ≤ $A[r][c]$ ≤ 100

Example

input

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

output

18

Solution & Inpression

삼성 SW 역량 테스트 기출 문제

2차원 배열을 5구역으로 나누는 부분에서 많이 방황하였다. 어렵다..... 인덱스 조작,

Code

언어 : JAVA

메모리 : 20,204 kb

실행시간 : 312 ms

import java.util.Scanner;

public class Main {
    static int N, min;
    static int[][] map;
    static int[] point;
    static int[] sum;

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

    N = 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();
        }
    }
    sc.close();
    min = Integer.MAX_VALUE;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
        point = new int[] { i, j };
        solve(point);
        }
    }
    System.out.println(min);
    }

    private static void solve(int[] point) {
    for (int d1 = 0; d1 < N; d1++) {
        for (int d2 = 0; d2 < N; d2++) {
        if ((0 <= d1 && 0 <= d2) && (0 <= point[0] && point[0] < point[0] + d1 + d2 && point[0] + d1 + d2 < N)
            && (0 <= point[1] - d1 && point[1] - d1 < point[1] && point[1] < point[1] + d2
                && point[1] + d2 < N)) {
            // System.out.println(Arrays.toString(point) + " " + d1 + " " + d2);
            int res = div(d1, d2);
            if (min > res)
            min = res;
        }
        }
    }
    }

    private static int div(int d1, int d2) {
    sum = new int[5];
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
        if ((Math.abs(r - 0) + Math.abs(c - 0)) >= point[0] + point[1])
            if ((Math.abs(r - 0) + Math.abs(c - 0)) <= point[0] + point[1] + 2 * d2)
            if ((Math.abs(r - 0) + Math.abs(c - N)) >= (N - point[1]) + point[0])
                if ((Math.abs(r - 0) + Math.abs(c - N)) <= (N - point[1]) + point[0] + 2 * d1) {
                // map[r][c] = 5;
                sum[4] += map[r][c];
                continue;
                }

        if (0 <= r && r < point[0] + d1 && 0 <= c && c <= point[1]) {
            // map[r][c] = 1;
            sum[0] += map[r][c];
        } else if (0 <= r && r <= point[0] + d2 && point[1] < c && c < N) {
            // map[r][c] = 2;
            sum[1] += map[r][c];
        } else if (point[0] + d1 <= r && r <= N && 0 <= c && c < point[1] - d1 + d2) {
            // map[r][c] = 3;
            sum[2] += map[r][c];
        } else if (point[0] + d2 <= r && r <= N && point[1] - d1 + d2 <= c && c < N) {
            // map[r][c] = 4;
            sum[3] += map[r][c];
        }
        }
    }
    int min = sum[0];
    int max = sum[0];
    for (int i = 1; i < 5; i++) {
        if (min > sum[i])
        min = sum[i];
        if (max < sum[i])
        max = sum[i];
    }

    return max - min;
    }

}

[BOJ] 17825. 주사위 윷놀이 - 중복순열

제출일 : 2019-11-11

문제 풀이 시간 : 5H

난이도 : ★★★★☆

Problem

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

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다.

게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에는 그 칸으로 이동할 수 없다. 시작과 도착칸은 말이 이미 있어도 이동할 수 있다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다.

말이 도착으로 이미 이동한 경우에는 더 이상 이동할 수 없고, 말이 이동하려고 하는 칸이 도착을 넘어가는 경우에는 도착에서 이동을 마친다.

주사위에서 나올 수 10개를 미리 알고있을때, 얻을 수 있는 점수의 최댓값을 구해보자.

Input

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

Output

얻을 수 있는 점수의 최댓값을 출력한다.

Example

input

1 2 3 4 1 2 3 4 1 2

output

190

Solution & Inpression

삼성 SW 역량 테스트 기출 문제

움직일수 있는 길은 4가지 경우로

모든 경우의 수($4^{10}=1,048,576$)를 중복순열을 이용하여 구한뒤 중복되는 경우는 버리고 최대값을 구하여 해결하였다.

중복되는 경우의 수가 일반적인 경우에는 움직이고 있는길과 현재 위치가 같을 경우이지만

마지막 25, 30, 34, 40은 움직이는 길이 다르더라도 같은 위치일 수 있다

이경우는 하드코딩으로 예외처리를 하였다.

이 문제를 풀며 난관에 여러번 부딛혔는다.

1. 문제를 이해하는데 많은 시간이 소요되었고
2. 중복을 처리할때 같은 경로가 아니더라도 같은 위치일 수 있고
3. 중복되는 경우는 제외해야 한다.

위 3가지를 고려했다면 더 빠른 시간내에 해결 할 수 있지 않았을까??

Code

언어 : JAVA

메모리 : 158,884 kb

실행시간 : 1,124 ms

import java.util.Scanner;

public class Main {
    static int[] route0 = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40 };
    static int[] route1 = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40 };
    static int[] route2 = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40 };
    static int[] route3 = { 0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40 };

    static int[] cmd;
    static int[] move;
    static int[][] horse;

    static int max;

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

        cmd = new int[10];
        for (int i = 0; i < 10; i++) { // 입력되는 명령어의 수 10개
            cmd[i] = sc.nextInt();
        }
        sc.close();
        // 입력 끝

        move = new int[10];
        max = Integer.MIN_VALUE;
        DFS(0);
        System.out.println(max);
    }

    private static void DFS(int depth) {
        if (depth == cmd.length) {
            int sum = solve();
            if (max < sum)
                max = sum;
            return;
        }

        for (int i = 0; i < 4; i++) {
            move[depth] = i;
            DFS(depth + 1);
        }

    }

    private static int solve() {
        horse = new int[4][2]; // 말의 위치, 가는 길, 움직인 횟수
        int sum = 0;

        for (int i = 0; i < 10; i++) {
            int cur = move[i]; // 현재움직일 말의 번호.
            horse[cur][0] += cmd[i]; // 움직였을때의 위치.
            int tmp = horse[cur][1];

            // ================길 변경================
            if (horse[cur][1] == 0) {
                if (horse[cur][0] == 5)
                    horse[cur][1] = 3;
                else if (horse[cur][0] == 10)
                    horse[cur][1] = 2;
                else if (horse[cur][0] == 15)
                    horse[cur][1] = 1;
            }

            // ================중복체크================
            boolean flag = false;
            int j = 0;
            for (; j < horse.length; j++) {
                if (cur != j) {
                    if (horse[cur][0] == horse[j][0] && horse[cur][1] == horse[j][1]) {
                        flag = true;
                        break;
                    } else if ((horse[cur][1] == 1 && horse[cur][0] == 19) || (horse[cur][1] == 2 && horse[cur][0] == 13)
                            || (horse[cur][1] == 3 && horse[cur][0] == 9)) {
                        // 25번에 도착했을때
                        if (horse[j][1] == 1 && horse[j][0] == 19) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 13) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 9) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    } else if ((horse[cur][1] == 1 && horse[cur][0] == 20) || (horse[cur][1] == 2 && horse[cur][0] == 14)
                            || (horse[cur][1] == 3 && horse[cur][0] == 10)) {
                        // 30번에 도착했을때
                        if (horse[j][1] == 1 && horse[j][0] == 20) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 14) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 10) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    }

                    else if ((horse[cur][1] == 1 && horse[cur][0] == 21) || (horse[cur][1] == 2 && horse[cur][0] == 15)
                            || (horse[cur][1] == 3 && horse[cur][0] == 11)) {
                        // 35번에 도착했을때
                        if (horse[j][1] == 1 && horse[j][0] == 21) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 15) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 11) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    } else if ((horse[cur][1] == 0 && horse[cur][0] == 20) || (horse[cur][1] == 1 && horse[cur][0] == 22)
                            || (horse[cur][1] == 2 && horse[cur][0] == 16) || (horse[cur][1] == 3 && horse[cur][0] == 12)) {
                        // 40번에 도착했을때
                        if (horse[j][1] == 0 && horse[j][0] == 20) {// 0번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 1 && horse[j][0] == 22) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 16) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 12) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    }
                }
            }
            if (flag) {
                return Integer.MIN_VALUE;
            }

            // ================더하기================
            if (horse[cur][1] == 0 && horse[cur][0] < route0.length)
                sum += route0[horse[cur][0]];
            else if (horse[cur][1] == 1 && horse[cur][0] < route1.length)
                sum += route1[horse[cur][0]];
            else if (horse[cur][1] == 2 && horse[cur][0] < route2.length)
                sum += route2[horse[cur][0]];
            else if (horse[cur][1] == 3 && horse[cur][0] < route3.length)
                sum += route3[horse[cur][0]];
        }
        return sum;
    }

}

[BOJ] 17822. 원판돌리기 - Simulation(BFS)

제출일 : 2019-11-11

문제 풀이 시간 : 1H 30M

난이도 : ★★★☆

Problem

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

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키지 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

Input

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

Output

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

Constraints

• 2 ≤ N, M, T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

Example

input

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

output

30

Solution & Inpression

삼성 SW 역량 테스트 기출 문제

시뮬레이션으로 문제에 주어진데로 풀면 되지만 조건이 까다롭고 어려웠던 문제.

Code

언어 : JAVA

메모리 : 30,488 kb

실행시간 : 280 ms

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

public class Main {
    static int N, M, T;
    static int[][] map;
    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);

        N = sc.nextInt() + 1; // 원판의 개수
        M = sc.nextInt(); // 각 원판의 정수의 개수
        T = sc.nextInt(); // 테스트 케이스 개수

        map = new int[N][M];

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        // 입력끝
        for (int i = 0; i < T; i++) {
            int x = sc.nextInt(); // 번호가 x의 배수인 원판을
            int d = sc.nextInt(); // d방향으로 (0:시계방향, 1:반시계방향)
            int k = sc.nextInt(); // k칸 회전시킨다.
            rotate(x, d, k);
            if (!check())
                edit();
        }
        System.out.println(sum());

        sc.close();
    }

    private static void edit() {
        int sum = 0, cnt = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    cnt++;
                    sum += map[i][j];
                }
            }
        }
        if (cnt == 0)
            return;
        double avg = sum / (double) cnt;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    if (map[i][j] > avg) // 평균보다 큰수
                        map[i][j]--; // 1을 빼고
                    else if (map[i][j] < avg)
                        map[i][j]++; // 1을 더한다
                }
            }
        }
    }

    private static boolean check() {
        boolean flag = false;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    if (bfs(i, j, map[i][j])) {
                        map[i][j] = 0;
                        flag = true;
                    }
                }
            }
        }
        return flag;
    }

    private static boolean bfs(int i, int j, int k) {
        Queue<int[]> q = new LinkedList<>();
        boolean flag = false;
        q.offer(new int[] { i, j });

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int r = cur[0] + dr[dir];
                int c = cur[1] + dc[dir];
                if (c == -1)
                    c = M - 1;
                else if (c == M)
                    c = 0;
                if (isRange(r, c)) {
                    if (map[r][c] == k) {
                        q.offer(new int[] { r, c });
                        map[r][c] = 0;
                        flag = true;
                    }
                }
            }
        }
        return flag;
    }

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

    private static int sum() {
        int sum = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sum += map[i][j];
            }
        }
        return sum;
    }

    private static void rotate(int x, int d, int k) {
        for (int num = x; num < N; num += x) {
            int cnt = k;
            while (cnt-- != 0) { // k칸 회전
                int[] tmp = map[num].clone();// 맵 복사
                switch (d) {
                case 0: // 시계방향 회전(오른쪽으로)
                    for (int j = 0; j < M - 1; j++) {
                        map[num][j + 1] = tmp[j];
                    }
                    map[num][0] = tmp[M - 1];
                    break;
                case 1: // 반시계방향 회전(왼쪽으로)
                    for (int j = 0; j < M - 1; j++) {
                        map[num][j] = tmp[j + 1];
                    }
                    map[num][M - 1] = tmp[0];
                    break;
                }
            }
        }
    }

}

[BOJ] 4195. 친구 네트워크 - UnionFind

제출일 : 2019-11-03

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

Example

input

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

output

2
3
4
2
2
4

Solution & Inpression

Union-Find를 활용한 문제

Code

언어 : JAVA

메모리 : 105,164 kb

실행시간 : 1500 ms

import java.io.FileInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<String, Integer> map;
    static int[][] parent;

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

        int T = sc.nextInt(); // 테스트 케이스의 개수 T

        for (int tc = 1; tc <= T; tc++) {

            int F = sc.nextInt();// 친구 관계 수 F <= 100,000
            makeSet(2 * F);
            map = new HashMap<>();

            for (int i = 0; i < F; i++) {
                String id1 = sc.next();
                String id2 = sc.next();

                if (!map.containsKey(id1))
                    map.put(id1, map.size());
                if (!map.containsKey(id2))
                    map.put(id2, map.size());

                System.out.println(union(map.get(id1), map.get(id2)));
            }

        } // end of TC
    }// end of Main

    private static void makeSet(int n) {
        parent = new int[n][2];
        for (int i = 0; i < parent.length; i++) {
            parent[i][0] = i; // i의 부모는 i
            parent[i][1] = 1; // i집합의 크기는 1;
        }
    }

    private static int union(int a, int b) {
        int x = find(a);
        int y = find(b);

        if (x != y) {
            if (x < y) {
                parent[y][0] = x;
                return parent[x][1] += parent[y][1];
            } else {
                parent[x][0] = y;
                return parent[y][1] += parent[x][1];
            }
        }
        return parent[x][1];

    }

    private static int find(int x) {
        if (x == parent[x][0])
            return x;
        else
            return parent[x][0] = find(parent[x][0]);
    }

}

[SWEA] 5658. 보물상자 비밀번호 - Simulation

제출일 : 2019-09-03

Problem

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

Input

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N과 크기 순서 K가 주어 진다.

그 다음 줄에는 16진수 0~F 숫자가 공백 없이 N개 주어진다.

Output

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

Example

input

5
12 10
1B3B3B81F75E
16 2
F53586D76286B2D8
…

output

#1 503
#2 55541
#3 334454
#4 5667473
#5 182189737

Code

언어 : JAVA

메모리 : 30,296 kb

실행시간 : 130ms

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

public class Solution {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            System.out.print("#" + tc + " ");
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int M = N / 4;
            ArrayList<Character> list = new ArrayList<>();
            String str = br.readLine();
            for (int i = 0; i < N; i++) {
                list.add(str.charAt(i));
            }
            ArrayList<String> numlist = new ArrayList<>();
            str = "";
            for (int i = 1; i <= N; i++) {
                str += list.get(i - 1);
                if (i % M == 0) {
                    if (!numlist.contains(str))
                        numlist.add(str);
                    str = "";
                }
            }

            for (int i = 1; i <= M - 1; i++) {
                char tmp = list.get(0);
                list.remove(0);
                list.add(tmp);
                str = "";
                for (int j = 1; j <= N; j++) {
                    str += list.get(j - 1);
                    if (j % M == 0) {
                        if (!numlist.contains(str))
                            numlist.add(str);
                        str = "";
                    }
                }
            }

            Collections.sort(numlist, new Comparator<String>() { // 역정렬
                @Override
                public int compare(String o1, String o2) {
                    int x = Integer.parseInt(o1, 16);
                    int y = Integer.parseInt(o2, 16);
                    return y - x;
                }
            });

            System.out.println(Integer.parseInt(numlist.get(K-1), 16));

        } // end of TC
    }// end of main
}

[SWEA] 6109. 추억의 2048게임 D4 - Simulation

제출일 : 2019-11-03

문제 풀이 시간 : 1H 30M

난이도 : ★★★

Problem

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

Input

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1≤N≤20)과 하나의 문자열 S가 공백 하나로 구분되어 주어진다.

S는 “left”, “right”, “up”, “down”의 넷 중 하나이며 각각 타일들을 왼쪽, 오른쪽, 위쪽, 아래쪽으로 이동시키겠다는 뜻이다.

다음 N개의 줄의 i번째 줄에는 N개의 정수가 공백 하나로 구분되어 주어진다.

이 정수들은 0이거나 2이상 1024이하의 2의 제곱수들이다.

i번째 줄의 j번째 정수는 격자의 위에서 i번째 줄의 왼쪽에서 j번째에 있는 칸에 있는 타일에 어떤 정수가 적혀 있는지 나타내며,

0이면 이 칸에 타일이 없음을 의미한다.

Output

각 테스트 케이스마다 ‘#t’(t는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 줄을 띄운 후,

N줄에 걸쳐 격자의 어떤 위치에 어떤 숫자가 적힌 타일이 있는지 입력 형식과 같은 형식으로 출력한다.

Example

input

2
5 up
4 8 2 4 0
4 4 2 0 8
8 0 2 4 4
2 2 2 2 8
0 2 2 0 0
2 down
16 2
0 2

output

#1
8 8 4 8 8
8 4 4 2 4
2 4 2 0 8
0 0 0 0 0
0 0 0 0 0
#2
0 0
16 4

Solution & Inpression

시뮬레이션 문제

차근차근 구현하면 되는 문제......

Code

언어 : JAVA

메모리 : 73,768 kb

실행시간 : 363 ms

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

public class Solution {

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            String cmd = sc.next();
            int[][] in = new int[N][N];
            int[][] out = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    in[i][j] = sc.nextInt();
                }
            }
            switch (cmd) {
            case "up":
                for (int j = 0; j < N; j++) { // 열 우선 탐색
                    for (int i = 0; i < N - 1; i++) { // 위부터 아래로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = i + 1;

                        while (in[idx][j] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == N - 1) // 끝까지 탐색
                                break;
                            idx++;
                        }

                        if (in[idx][j] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[idx][j]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[idx][j] = 0;
                            i = idx;
                        }
                    }
                    int cur = 0;
                    for (int i = 0; i < N; i++) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[cur++][j] = in[i][j];
                        }
                    }
                }
                break;
            case "down":
                for (int j = 0; j < N; j++) { // 열 우선 탐색
                    for (int i = N - 1; i > 0; i--) { // 아래부터 위
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = i - 1;

                        while (in[idx][j] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == 0) // 끝까지 탐색
                                break;
                            idx--;
                        }

                        if (in[idx][j] == 0) // 비교할 값이 0이면 패스
                            continue;
                        if (in[i][j] == in[idx][j]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[idx][j] = 0;
                            i = idx;
                        }

                    }
                    int cur = N - 1;
                    for (int i = N - 1; i >= 0; i--) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[cur--][j] = in[i][j];
                        }
                    }
                }
                break;
            case "left":
                for (int i = 0; i < N; i++) { // 행우선 탐색
                    for (int j = 0; j < N - 1; j++) { // 왼쪽부터 오른쪽으로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = j + 1;

                        while (in[i][idx] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == N - 1) // 끝까지 탐색
                                break;
                            idx++;
                        }

                        if (in[i][idx] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[i][idx]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[i][idx] = 0;
                            j = idx;
                        }
                    }
                    int cur = 0;
                    for (int j = 0; j < N; j++) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[i][cur++] = in[i][j];
                        }
                    }
                }
                break;

            case "right":
                for (int i = 0; i < N; i++) { // 행우선 탐색
                    for (int j = N-1; j > 0; j--) { // 오른쪽 부터 왼쪽으로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = j - 1;

                        while (in[i][idx] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == 0) // 끝까지 탐색
                                break;
                            idx--;
                        }

                        if (in[i][idx] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[i][idx]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[i][idx] = 0;
                            j = idx;
                        }
                    }
                    int cur = N-1;
                    for (int j = N-1; j >=0 ; j--) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[i][cur--] = in[i][j];
                        }
                    }
                }
                break;

            }

            System.out.println("#" + tc);
            for (int[] is : out) {
                for (int i : is) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }

        } // end of TC
    }// end of Main
}