[BOJ] 1339. 단어 수학 (Java)

Problem

제출일 : 2020-03-10

문제 풀이 시간 : 4H

난이도 : ★★☆

---

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

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

Input

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

Output

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

Example

input

2
GCF
ACDEB

output

99437

Solution & Inpression

HashMap을 이용하여 사용된 알파벳의 개수를 구한뒤

순열을 이용하여 완전탐색 후 값 계산

최대값 갱신의 순으로 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 19080 kb

실행 시간 : 1408 ms

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

public class Main {
    static int N, max;
    static String[] words;

    static Map<Character, Integer> alphabet;
    static boolean[] visit;
    static int[] data;

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

        words = new String[N];

        alphabet = new HashMap<Character, Integer>();
        int count = 0;
        for (int i = 0; i < N; i++) {
            words[i] = sc.next();
            for (int j = 0; j < words[i].length(); j++) {
                if (!alphabet.containsKey(words[i].charAt(j))) {
                    alphabet.put(words[i].charAt(j), count++);
                }
            }
        }
        data = new int[alphabet.size()];
        visit = new boolean[10];
        max = Integer.MIN_VALUE;
        solve(0, 0);
        System.out.println(max);
    }

    private static void solve(int index, int depth) {
        if (depth == data.length) {
            check();
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (!visit[i]) {
                visit[i] = true;
                data[depth] = i;
                solve(i, depth + 1);
                visit[i] = false;
            }
        }
    }

    private static void check() {
        int ret = 0;
        for (int i = 0; i < words.length; i++) {
            int tmp = 0;
            for (int j = 0; j < words[i].length(); j++) {
                tmp += data[alphabet.get(words[i].charAt(j))];
                tmp *= 10;
            }
            ret += tmp / 10;
        }
        if (max < ret)
            max = ret;
    }
}

[BOJ] 6064. 카잉 달력(Java)

Problem

제출일 : 2020-03-10

문제 풀이 시간 : 4H

난이도 : ★★★★☆

---

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

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

Input

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

Output

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

Example

input

3
10 12 3 9
10 12 7 2
13 11 5 6

output

33
-1
83

Solution & Inpression

나머지 연산의 특징을 이용하여 문제를 해결하였다.

x값에 M을 더하여 M으로 나누는 나머지 연산을 수행한 결과와 x를 M으로 나누는 나머지 연산을 수행한 결과가 같기 때문에 x값에 M만큼 증가시키며 해당 값이 N으로 나누었을때의 나머지가 y값과 같은지를 검사하였다.

코드상에서 (year % N) == 0 ? N : year % N 부분은 10%10의 결과가 10이 아닌 0이기에 위와같이 처리해주었다.

나머지 연산의 특징

a를 b로 나눈 나머지를 a mod b 할때 나머지는 다음과 같은 식들이 항상 성립합니다.

$1.\ (a+m)\mod m=a \mod m$

$ 2.\ ((a\mod m) + ( b\mod m) ) \mod m = ( a + b ) \mod m $

$3.\ ( ( a \mod m) \times ( b \mod m) ) \mod m = ( a \times b) \mod m $

Code

언어 : JAVA

메모리 : 23080 kb

실행 시간 : 352 ms

package BOJ.Math;
import java.util.Scanner;

public class Silver1_6064_카잉달력 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            int M = sc.nextInt();
            int N = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            int year = x;
            int max = lcm(M, N);

            while (true) {
                if (year > max) {
                    System.out.println("-1");
                    break;
                } else if (((year % N) == 0 ? N : year % N) == y) {
                    System.out.println(year);
                    break;
                }
                year += M;
            }
        }
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

Reference

6064번 : 카잉 달력|작성자 DolphaGo

[BOJ] 3055. 탈출 (Java)

Problem

제출일 : 2020-03-08

문제 풀이 시간 : 2H

난이도 : ★★☆

---

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

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

Input

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

Output

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

Example

input

3 3
D.*
...
.S.

output

3

Solution & Inpression

문제를 읽어보면 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.

물을 먼저 이동시키고 이후 고슴도치를 이동시켜야 하는 것을 알 수 있다.

각각을 다른 큐에 넣어 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 14624 kb

실행 시간 :120 ms

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

public class Main {
    static int R, C, ans;
    static char[][] map;

    static Queue<int[]> me, water;
    static int[] end;

    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);
        R = sc.nextInt();
        C = sc.nextInt();

        map = new char[R][C];
        me = new LinkedList<>();
        water = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            String str = sc.next();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'S') {
                    me.add(new int[] { i, j, 0 });
                    map[i][j] = '.';
                } else if (map[i][j] == 'D') {
                    end = new int[] { i, j };
                } else if (map[i][j] == '*') {
                    water.add(new int[] { i, j });
                }
            }
        }
        ans = -1;
        BFS();
        System.out.println(ans == -1 ? "KAKTUS" : ans);

    }

    private static void BFS() {
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visit = new boolean[R][C];

        visit[me.peek()[0]][me.peek()[1]] = true;

        while (!me.isEmpty() || !water.isEmpty()) {
            while (!water.isEmpty()) {
                q.offer(water.poll());
            }

            while (!q.isEmpty()) {
                // 물의 움직임
                int[] now = q.poll();
                for (int dir = 0; dir < dr.length; dir++) {
                    int nr = now[0] + dr[dir];
                    int nc = now[1] + dc[dir];
                    if (isRange(nr, nc) && (map[nr][nc] == '.')) {
                        water.add(new int[] { nr, nc });
                        map[nr][nc] = '*';
                    }
                }
            }

            while (!me.isEmpty()) {
                q.offer(me.poll());
            }

            while (!q.isEmpty()) {
                // 비버의 움직임
                int[] now = q.poll();
                if (now[0] == end[0] && now[1] == end[1]) {
                    ans = now[2];
                    return;
                }
                for (int dir = 0; dir < dr.length; dir++) {
                    int nr = now[0] + dr[dir];
                    int nc = now[1] + dc[dir];
                    if (isRange(nr, nc) && !visit[nr][nc])
                        if (map[nr][nc] == '.' || map[nr][nc] == 'D') {
                            me.add(new int[] { nr, nc, now[2] + 1 });
                            visit[nr][nc] = true;
                        }
                }
            }
        }

    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < R && 0 <= nc && nc < C)
            return true;
        return false;
    }
}

[BOJ] 2206. 벽 부수고 이동하기 (Java)

Problem

제출일 : 2020-03-07

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

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

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

input

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

Output

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

Example

input

6 4
0100
1110
1000
0000
0111
0000

output

15

Solution & Inpression

[Hint][https://www.acmicpc.net/board/view/27386]

1. 가중치가 없는 최단 경로는 무조건 BFS입니다. 왜 DFS가 안 될까요? 그 이유는 당연하게도, 특정 칸에 처음 도달했을 때까지의 경로의 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장이 전혀 없기 때문입니다. 아직까지 이 사실을 모르고 계셨다면, 이 문제는 아직 풀기에 너무 어렵습니다. 더 기본적인 BFS 문제들을 먼저 풀어보세요.

2. 모든 칸을 전부 0으로 하나씩 바꾸어보고 BFS를 돌리는 것을 반복해서는 통과될 수 없습니다. 대부분의 알고리즘 문제가 그렇듯이, 풀이를 짜기 전에 반드시 해야 하는 것 중 하나는 시간 복잡도를 생각하는 것입니다. 시간 복잡도 계산, 전혀 어렵지 않습니다. 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색해야 하죠? 그러니 O((NM)^2)입니다. 이 수는 우리가 대충 1초에 돌 수 있다고 보는 단위인 1억을 10000배나 뛰어넘는 1조입니다. 절대 통과될 수 없겠죠?

3. 칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다.

Code

언어 : JAVA

메모리 : 137144 kb

실행 시간 : 628 ms

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

public class Main {
    static int N, M, ans;
    static char[][] map;

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

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

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

        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        ans = -1;
        BFS();
        System.out.println(ans);
    }

    private static void BFS() {
        boolean visit[][][] = new boolean[2][N][M];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { 0, 0, 0, 1 });
        visit[0][0][0] = true;

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

            if (now[0] == N - 1 && now[1] == M - 1) {
                ans = now[3];
                break;
            }

            for (int dir = 0; dir < 4; dir++) {
                int nr = now[0] + dr[dir];
                int nc = now[1] + dc[dir];
                if (isRange(nr, nc) && !visit[now[2]][nr][nc]) {
                    if (map[nr][nc] == '0') {
                        visit[now[2]][nr][nc] = true;
                        q.offer(new int[] { nr, nc, now[2], now[3] + 1 });
                    } else if (now[2] == 0) {
                        visit[1][nr][nc] = true;
                        q.offer(new int[] { nr, nc, 1, now[3] + 1 });
                    }
                }
            }
        }
    }

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

[BOJ] 14503. 로봇 청소기 (Java)

Problem

제출일 : 2020-03-07

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

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

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

input

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

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 장소의 모든 외곽은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

Output

로봇 청소기가 청소하는 칸의 개수를 출력한다.

Example

input

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

output

57

Solution & Inpression

시뮬레이션 문제

시간이 생각보다 오래 걸렸다. 문제를 로봇 청소기가 움직이는 방법에 따라 모두 함수로 구현하고 이를 재귀로 호출하여 문제를 해결하려 했다. 생각보다 코드가 많이 지저분해지며 종료 조건이 까다로워 구현이 힘들었다.

생각보다 간단한 방법으로 문제를 해결할 수 있었다.......

Code

언어 : JAVA

메모리 : 19168 kb

실행 시간 : 172 ms

import java.util.Scanner;

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

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

    static int ans;

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

        int r = sc.nextInt();
        int c = sc.nextInt();
        int dir = sc.nextInt();

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                map[i][j] = sc.nextInt();
        }
        ans = 0;
        solve(r, c, dir);

        System.out.println(ans);
    }

    static void solve(int r, int c, int dir) {

        switch (map[r][c]) {
        case 1:
            return;
        case 0:
            map[r][c] = -1;
            ans++;
        }
        int nDir = dir;
        for (int i = 0; i < 4; i++) {
            nDir = (nDir + 3) % 4;
            int nR = r + dr[nDir];
            int nC = c + dc[nDir];

            if (map[nR][nC] == 0) {
                solve(nR, nC, nDir);
                return;
            }
        }
        solve(r - dr[dir], c - dc[dir], dir);
        return;
    }
}

[BOJ] 2178. 미로 탐색 (Java)

Problem

제출일 : 2020-02-27

문제 풀이 시간 : 30M

난이도 : ★

---

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

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

input

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

Output

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

Example

input

4 6
101111
101010
101011
111011

output

15

Solution & Inpression

BFS 기본문제

Code

언어 : JAVA

메모리 : 19064 kb

실행시간 : 152 ms

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

public class Main {
    static int N, M;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

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

        char[][] maze = new char[N][M];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                maze[i][j] = str.charAt(j);
            }
        }
        int[][] visit = new int[N][M];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { 0, 0 });
        visit[0][0] = 1;

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

            for (int dir = 0; dir < dr.length; dir++) {
                int r = cur[0] + dr[dir];
                int c = cur[1] + dc[dir];
                if (isRange(r, c) && visit[r][c] == 0 && maze[r][c] == '1') {
                    q.offer(new int[] { r, c });
                    visit[r][c] = visit[cur[0]][cur[1]] + 1;
                }
            }
        }
        System.out.println(visit[N - 1][M - 1]);
    }

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

[BOJ] 1707. 이분그래프 (Java)

Problem

제출일 : 2020-02-27

문제 풀이 시간 : 30M

난이도 : ★☆

---

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

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

input

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

Output

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

Example

input

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

output

YES
NO

Solution & Inpression

주어진 그래프가 이분 그래프인지 확인하는 방법은 각 정점들을 BFS나 DFS를 이용하여 정점을 탐색해나아가며 색을 칠하며 같은 색의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다.

문제를 풀때 주의 해야할 점은 1번 정점만을 탐색한다해서 모든 정점을 순회할 수 없는 테스트케이스가 있기 때문에 모든 정점을 탐색할 수 있도록 구현해야한다.

Code

언어 : JAVA

메모리 : 314196 kb

실행시간 : 2804 ms

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

public class Main {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        for (int tc = 0; tc < K; tc++) {
            int V = sc.nextInt();
            int E = sc.nextInt();

            LinkedList<Integer>[] graph = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                graph[i] = new LinkedList<>();
            }
            for (int i = 0; i < E; i++) {
                int s = sc.nextInt() - 1;
                int e = sc.nextInt() - 1;
                graph[s].add(e);
                graph[e].add(s);
            }

            boolean flag = true;
            int[] visit = new int[V];
            Queue<Integer> q = new LinkedList<>();

            for (int i = 0; i < V; i++) {
                if (visit[i] == 0) {
                    q.offer(i);
                    visit[i] = 1;

                    while (!q.isEmpty() && flag) {
                        int cur = q.poll();
                        for (Integer next : graph[cur]) {
                            if (visit[next] == 0) {
                                q.offer(next);
                                visit[next] = visit[cur] * -1;
                            } else if (visit[next] == visit[cur]) {
                                flag = false;
                                break;
                            }
                        }
                    }

                }
            }
            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

[BOJ] 2933. 미네랄- Simulation (Java)

Problem

제출일 : 2020-02-25

문제 풀이 시간 : 4H

난이도 : ★★★

---

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

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

input

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터의 맨 아래 부분이 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

Output

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

Example

input

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

output

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

Solution & Inpression

BFS + 시뮬레이션 문제

시뮬레이션 문제는 문제를 이해하는 시간이 오래걸리고 그에 맞게 구현하기 위한 아이디어를 생각해내는데 시간이 오래걸린다. 오랜만에 구현이 까다로운 문제를 푼것 같다.

다음에 기회가 된다면 리펙토링을 하여 다시 문제를 풀어봐야겠다.

Code

언어 : JAVA

메모리 : 54368 kb

실행시간 : 468 ms

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

public class Main {
    static int R, C, cnt;
    static char[][] map;
    static int[][] visit;

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

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new char[R][C];
        cnt = 0;
        for (int i = 0; i < R; i++) {
            String str = sc.next();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'x')
                    cnt++;
            }
        }
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int floor = R - sc.nextInt();
            if (i % 2 == 0) {
                // 왼쪽에서 오른쪽으로 이동
                for (int j = 0; j < C; j++) {
                    if (map[floor][j] == 'x') {
                        map[floor][j] = '.';
                        cnt--;
                        break;
                    }
                }
            } else {
                // 오른쪽에서 왼쪽으로 이동
                for (int j = C - 1; j >= 0; j--) {
                    if (map[floor][j] == 'x') {
                        map[floor][j] = '.';
                        cnt--;
                        break;
                    }
                }
            }
            if (cnt != BFS()) {
                down();
            }

        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    private static void down() {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'x' && visit[i][j] == 0) { // 공중에 떠있는 클러스터 표시
                    visit[i][j] = 2;
                    q.add(new int[] { i, j });

                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        for (int dir = 0; dir < dr.length; dir++) {
                            int r = cur[0] + dr[dir];
                            int c = cur[1] + dc[dir];
                            if (isRange(r, c) && map[r][c] == 'x' && visit[r][c] == 0) {
                                visit[r][c] = 2;
                                q.add(new int[] { r, c });
                            }
                        }
                    } // end of while
                }
            }
        } // 표시 끝

        // 내리자(몇칸????)
        int h = 1234567890;
        int cnt = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (visit[i][j] == 2) { // 내려갈 수 있는 값을 구한다.
                    cnt = 0;
                    for (int r = i + 1; r < R; r++) {
                        if (visit[r][j] == 1) {
                            // 아랫칸이 같은 클러스터가 아니라면
                            break;
                        } else if (visit[r][j] == 2) {
                            cnt = h;
                            break;
                        } else
                            cnt++;
                    }
                    if (h > cnt)
                        h = cnt;
                } // end of if
            }
        }

        // h칸만큼 내린다.
        for (int i = R - 1; i >= 0; i--) {
            for (int j = 0; j < C; j++) {
                if (visit[i][j] == 2) {
                    map[i][j] = '.';
                    map[i + h][j] = 'x';
                }
            }
        }

    }

    static int BFS() {
        int ret = 0;
        Queue<int[]> q = new LinkedList<>();
        visit = new int[R][C];

        for (int j = 0; j < C; j++) { // 바닥에 붙어있는 부분 만 검사
            if (map[R - 1][j] == 'x' && visit[R - 1][j] == 0) {
                visit[R - 1][j] = 1;
                ret++;
                q.add(new int[] { R - 1, j });

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    for (int dir = 0; dir < dr.length; dir++) {
                        int r = cur[0] + dr[dir];
                        int c = cur[1] + dc[dir];
                        if (isRange(r, c) && map[r][c] == 'x' && visit[r][c] == 0) {
                            visit[r][c] = 1;
                            ret++;
                            q.add(new int[] { r, c });
                        }
                    }
                } // end of while

            }
        }
        return ret;

    }

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

}