[BOJ] 13913. 숨바꼭질4- BFS (Java)

Problem

제출일 : 2020-02-22

문제 풀이 시간 : 1H

난이도 : ★★

---

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

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

input

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

Output

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

Example

input

5 17

output

4
5 10 9 18 17

Solution & Inpression

쉬운 BFS 문제 + 경로를 출력하는 문제

경로를 출력하는 부분에서

//                StringBuilder sb = new StringBuilder(cur + "");
//                while (path[cur] != cur) {
//                    sb.insert(0, " ").insert(0, path[cur]);
//                    cur = path[cur];
//                }
//                System.out.println(sb);

위와 같이 경로를 출력하였더니 시간초과가 발생하였다.

스텍 자료구조에 담고 append()를 이용하여 경로를 출력하니 시간 초과없이 문제를 해결할 수 있었다.

정확한 이유는 모르겠지만 insert의 위치가 0번째라 안의 값을 뒤로 미는 작업이 수행되는 것이 아닐까 하는 짐작을 한다.

정확한 이유를 알게되면 포스팅에 추가 하겠습니다. 혹시 정확한 이유를 아시는 분은 댓글로 알려주시면 감사하겠습니다.

Code

언어 : JAVA

메모리 : 47660 kb

실행시간 : 316 ms

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

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

        int[] visit = new int[100001];
        int[] path = new int[100001];

        Queue<Integer> q = new LinkedList<Integer>();
        visit[N] = 1;
        path[N] = N;
        q.offer(N);
        int next;

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

            if (cur == K) {
                System.out.println(visit[cur] - 1);

                Stack<Integer> stack = new Stack<>();
                while (path[cur] != cur) {
                    stack.add(cur);
                    cur = path[cur];
                }
                stack.add(N);

                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty())
                    sb.append(stack.pop() + " ");
                System.out.println(sb);

                return;
            }

            next = cur << 1;
            if (next <= 100000 && visit[next] == 0) {
                visit[next] = visit[cur] + 1;
                path[next] = cur;
                q.offer(next);
            }

            next = cur + 1;
            if (next <= 100000 && visit[next] == 0) {
                visit[next] = visit[cur] + 1;
                path[next] = cur;
                q.offer(next);
            }

            next = cur - 1;
            if (next >= 0 && visit[next] == 0) {
                visit[next] = visit[cur] + 1;
                path[next] = cur;
                q.offer(next);
            }

        }

    }
}

[SWEA] 7699. 수지의 수지 맞는 여행 (D4) (Java)

Problem

제출일 : 2020-02-18

문제 풀이 시간 : 15M

난이도 : ★

---

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

평소에 여행을 즐기는 수지는 이번에 새로운 섬에 도착했다.

이 섬은 1행, 1열로 시작해서 R행, C열까지 있으며, 총 R*C 칸으로 이루어져 있다.

수지는 지금 1행 1열에 있으며 앞으로 있을 야근을 위하여 기회 있을 때 미리 여행을 떠나려고 한다.

이 섬의 각 칸에는 알파벳이 적혀있다. 이 알파벳은 섬의 명물이고, 같은 알파벳은 같은 명물이다.

이 섬에서는 명물을 볼 때마다 요금을 지급해야 하는데 각 알파벳 명물을 처음 볼 땐 무료로 볼 수 있다.

그리고, 수지는 여행을 할 때 자신이 있는 지점의 명물을 본 후 4방향(상, 하, 좌, 우) 중 한 방향으로 1칸 이동 후 다음 명물을 보는 행동을 반복한다.

올해 SGA사 1년 차인 수지는 현재 대출빚과 카드빚에 허덕이고 있다.

따라서, 명물을 최대한 많이 보되, 요금을 지급하지 않는 방법을 택해야 한다.

수지가 1행 1열에서 여행을 시작했을 때, 같은 알파벳 명물을 두 번 이상 보지 않도록 여행을 떠나는 방법 중에 볼 수 있는 명물의 최대 개수를 구하여라.

input

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

각 테스트 케이스의 첫 번째 줄에는 섬의 크기 R,C(1≤R,C≤20)가 주어진다.

이어서 R개의 줄마다 C개의 알파벳 대문자가 빈 칸 없이 주어진다.

Output

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

각 테스트 케이스마다 수지가 여행하면서 볼 수 있는 명물 개수의 최대치를 출력하라.

Example

input

3
2 4
CAAB
ADCB
3 6
HFDFFB
AJHGDH
DGAGEH
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

output

#1 3
#2 6
#3 10

Solution & Inpression

알파벳이 같으면 요금을 지불해야 되기때문에 가지 않았다. 따라서 방문 처리를 알파벳의 개수의 배열을 이용하여 방문처리를 하였고 항상 최대값을 갱신해주었다.

Code

언어 : JAVA

메모리 : 24,648 kb

실행시간 : 2,068 ms

import java.util.Scanner;

class Solution {
    static int T, R, C, ans;
    static char[][] map;
    static boolean[] visit;

    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();
        for (int tc = 1; tc <= T; tc++) {
            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 = new boolean[26];
            visit[map[0][0] - 'A'] = true;
            DFS(0, 0, 1);
            System.out.println("#" + tc + " " + ans);
        } // end of TC
    }

    private static void DFS(int i, int j, int depth) {
        if (depth > ans)
            ans = depth;
        for (int dir = 0; dir < dc.length; dir++) {
            int r = i + dr[dir];
            int c = j + dc[dir];
            if (isRange(r, c) && !visit[map[r][c] - 'A']) {
                visit[map[r][c] - 'A'] = true;
                DFS(r, c, depth + 1);
                visit[map[r][c] - 'A'] = false;
            }

        }
    }

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

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