[SWEA] 2819. 격자판의 숫자 이어 붙이기 (D4) (Java)

Problem

제출일 : 2020-02-18

문제 풀이 시간 : 15M

난이도 : ★

---

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

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.

격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.

input

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

각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.

Output

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.

Example

input

1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1

output

#1 23

Solution & Inpression

방문 처리를 하지 않고 6번까지 깊이 우선탐색후 HashSet 자료구조를 사용하여 중복을 제거하고 size를 출력하였다.

Code

언어 : JAVA

메모리 : 57,648 kb

실행시간 : 224 ms

import java.util.HashSet;
import java.util.Scanner;

class Solution {
    static int T, N;
    static HashSet<String> set;
    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);
        T = sc.nextInt();
        N = 4;

        for (int tc = 1; tc <= T; tc++) {
            map = new int[4][4];
            set = new HashSet<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    DFS(i, j, 0, "" + map[i][j]);
                }
            }
            System.out.println("#" + tc + " " + set.size());

        } // end of TC
    }

    private static void DFS(int i, int j, int depth, String str) {
        if (depth == 6) {
            set.add(str);
            return;
        }
        for (int dir = 0; dir < dc.length; dir++) {
            int r = i + dr[dir];
            int c = j + dc[dir];
            if (isRange(r, c)) {
                DFS(r, c, depth + 1, str + map[r][c]);
            }
        }
    }

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

[BOJ] 11724. 연결 요소의 개수- 그래프/BFS (Java)

Problem

제출일 : 2020-02-16

문제 풀이 시간 : 15M

난이도 : ★

---

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

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

input

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

Output

첫째 줄에 연결 요소의 개수를 출력한다.

Example

input

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

output

2

Solution & Inpression

문제에 설명이 자세하지 않아

연결요소라는 것을 찾아보고 이해한뒤 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 283,972 kb

실행시간 : 1,352 ms

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

public class Silver3_11724_연결요소 {
    static int N, M, ans;
    static boolean[][] graph;
    static boolean[] visit;

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

        N = sc.nextInt();
        M = sc.nextInt();
        graph = new boolean[N + 1][N + 1];
        visit = new boolean[N + 1];
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            graph[s][e] = true;
            graph[e][s] = true;
        }
        ans = 0;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                BFS(i);
                ans++;
            }
        }
        System.out.println(ans);
    }

    private static void BFS(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(x);
        visit[x] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 1; i <= N; i++) {
                if (!visit[i] && graph[cur][i]) {
                    visit[i] = true;
                    q.offer(i);
                }
            }
        }

    }
} 

[BOJ] 15651. N과 M (3) - 중복순열 (Java)

Problem

제출일 : 2020-02-16

문제 풀이 시간 : 15M

난이도 : ★

---

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

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

input

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

Output

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

Example

input

4 2

output

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

Solution & Inpression

N과M 세번째 문제

중복하여 선택이 가능하고 순서가 중요한것은 중복순열이다.

시간초과가 발생하여 StringBuilder을 이용하여 문제를 풀었습니다.

Code

언어 : JAVA

메모리 : 373,692 kb

실행시간 : 696 ms

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[] rlt;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        rlt = new int[M];
        solve(0, 0);
        System.out.println(sb);
    }

    private static void solve(int index, int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(rlt[i] + " ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            rlt[depth] = i + 1;
            solve(i, depth + 1);
        }

    }
} 

[BOJ] 11723. 집합 - 비트마스킹 (Java)

Problem

제출일 : 2020-02-16

문제 풀이 시간 : 15M

난이도 : ★

---

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

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다.
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

input

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

Output

check 연산이 주어질때마다, 결과를 출력한다.

Example

input

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

output

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

Solution & Inpression

비트마스킹문제지만 배열을 이용하여 문제를 풀었고 처음 제출했을때 시간 초과가 발생하여 StringBuilder 을 이용하여 출력시간을 줄여 문제를 해결하였습니다.

Code

언어 : JAVA

메모리 : 389,056 kb

실행시간 : 3,632 ms

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

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

        int M = sc.nextInt();
        boolean[] set = new boolean[21];
        for (int i = 0; i < M; i++) {
            switch (sc.next()) {
            case "add":
                set[sc.nextInt()] = true;
                break;
            case "remove":
                set[sc.nextInt()] = false;
                break;
            case "check":
                if (set[sc.nextInt()])
                    ans.append("1\n");
                else
                    ans.append("0\n");
                break;
            case "toggle":
                int tmp = sc.nextInt();
                set[tmp] = !set[tmp];
                break;
            case "all":
                Arrays.fill(set, true);
                break;
            case "empty":
                Arrays.fill(set, false);
                break;
            }
        }
         System.out.println(ans);
    }
}

[BOJ] 1987. 알파벳 (Java)

Problem

제출일 : 2020-02-14

문제 풀이 시간 : 30M

난이도 : ★★

---

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

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

input

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

Output

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

Example

input

2 4
CAAB
ADCB

output

3

Solution & Inpression

처음 문제를 읽었을때 DFS, BFS 어느 방법이든 문제를 해결할 수 있을것이라 생각했다.

하지만 BFS로는 백트레킹을 구현하기가 어려운 부분이 있어 DFS로 문제를 해결했고

답이 될 수 있는 최대값은 26으로 26이 넘는다면 더이상 탐색을 하지 않고 종료하는 것으로 시간을 줄일 수 있었다.

Code

언어 : JAVA

메모리 : 15,140 kb

실행시간 : 940 ms

import java.util.Scanner;

public class Main {
    static int R, C, ans;
    static char[][] map;
    static boolean[] visit = new boolean[26];
    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];
        for (int i = 0; i < R; i++) {
            String str = sc.next();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        ans = 0;
        visit[map[0][0] - 'A'] = true;
        DFS(0, 0, 1);
        System.out.println(ans);
    }

    private static void DFS(int i, int j, int cnt) {
        if (ans < cnt)
            ans = cnt;
        else if (ans == 26)
            return;
        for (int dir = 0; dir < dr.length; dir++) {
            int nr = i + dr[dir];
            int nc = j + dc[dir];

            if (isRange(nr, nc) && !visit[map[nr][nc] - 'A']) {
                visit[map[nr][nc] - 'A'] = true;
                DFS(nr, nc, cnt + 1);
                visit[map[nr][nc] - 'A'] = false;
            }
        }

    }

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

[BOJ] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - BF (Java)

Problem

제출일 : 2020-02-13

문제 풀이 시간 : 15M

난이도 : ☆

---

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

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

input

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

Output

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

Example

input

5 3
1 2
3 4
1 3

output

3

Solution & Inpression

순열을 이용하여 경우의 수를 구하고 금지된 조합일 경우 카운트를 하지 않는다.

Code

언어 : JAVA

메모리 : 34,032 kb

실행시간 : 104 ms

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static boolean[][] graph;
    static boolean[] visit;
    static int[] data = new int[3];

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

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

        graph = new boolean[N][N];
        visit = new boolean[N];

        for (int i = 0; i < M; i++) {
            int s = sc.nextInt() - 1;
            int e = sc.nextInt() - 1;
            graph[s][e] = true;
            graph[e][s] = true;
        }
        ans = 0;
        solve(0, 0);
        System.out.println(ans);

    }

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

    private static boolean check() {
        for (int i = 0; i < 2; i++) {
            for (int j = i + 1; j < 3; j++) {
                if (graph[data[i]][data[j]])
                    return false;
            }
        }
        return true;
    }
}

[BOJ] 4963. 섬의 개수 - DFS

Problem

제출일 : 2020-02-13

문제 풀이 시간 : 20M

난이도 : ★

---

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

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다.

input

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

Output

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

Example

input

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

output

0
1
1
3
1
9

Solution & Inpression

기본적인 DFS/BFS문제로 DFS나 BFS어떤 풀이를 사용하더라도 문제는 해결할 수 있다.

어렵거나 문제가 이해가 되지 않았던 부분이 없었기 때문에 쉽게 풀 수 있었다

단지 높이와 너비를 입력으로 주는 순서나 0 0이 종료조건이며 대각선 방향도 연결이 되있다는것을 파악하면 한번에 해결할 수 있을 것이라 생각한다.

Code

언어 : JAVA

메모리 : 32,616 kb

실행시간 : 312 ms

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

public class Main {
    static int W, H, ans;
    static int[][] map;
    // 상, 하, 좌, 우, 좌상, 좌하, 우상, 우하
    static int[] dr = { -1, 1, 0, 0, -1, 1, -1, 1 };
    static int[] dc = { 0, 0, -1, 1, -1, -1, 1, 1 };

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

        while (true) {
            W = sc.nextInt();
            if (W == 0)
                break;
            H = sc.nextInt();

            map = new int[H][W];

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            ans = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == 1) {
                        DFS(i, j);
                        ans++;

                    }
                }
            }
            System.out.println(ans);
        } // end of while

    }

    private static void DFS(int i, int j) {
        for (int dir = 0; dir < dc.length; dir++) {
            int nr = i + dr[dir];
            int nc = j + dc[dir];
            if (isRange(nr, nc) && map[nr][nc] == 1) {
                map[nr][nc] = 0;
                DFS(nr, nc);
            }
        }
    }

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

[BOJ] 1107. 리모컨 - BF

Problem

제출일 : 2020-02-13

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

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

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

input

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

Output

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

Example

input

500000
8
0 2 3 4 6 7 8 9

output

11117

Solution & Inpression

3번을 다시 풀어 통과한 문제

처음 문제를 접근할때 goal에 가장 근접한 값을 찾아 계산하려 했지만 생각보다 예외가 많아 완전 탐색을 수행했다.

입력으로 주어지는 최대 값은 500,000 으로 6자리의 숫자이기때문에 0~999999을 탐색을 수행했다.

2시간이 넘게 붙잡고 문제를 풀었지만 쉽게 푸려니 한없이 쉽게 풀어지는 문제라고 생각이 든다.

Code1

언어 : JAVA

메모리 : 109,160 kb

실행시간 : 384 ms

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

public class Main {
    static boolean[] broken;

    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int start = 100;
        int goal = sc.nextInt();
        if (start == goal) {
            System.out.println(0);
            return;
        }
        int N = sc.nextInt();
        broken = new boolean[10];
        for (int i = 0; i < N; i++) {
            broken[sc.nextInt()] = true;
        }
        int ans = Math.abs(goal - start);
        for (int i = 0; i <= 1000000; i++) { // 숫자 버튼으로 이동하는 채널
            if (go(i)) {
                int tmp = Math.abs(i - goal) + ("" + i).length(); // +나 -를 몇 번 눌러야 하는지 계산
                if (ans > tmp) {
                    ans = tmp;
                }
            }
        }
        System.out.println(ans);
    }

    private static boolean go(int x) {
        String str = "" + x;
        for (int i = 0; i < str.length(); i++) {
            if (broken[str.charAt(i) - '0'])
                return false;
        }
        return true;
    }
}