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

[BOJ] 9944. NxM 보드 완주하기

Problem

제출일 : 2020-02-13

문제 풀이 시간 : 1H 30M

난이도 : ★★★☆

---

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

N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다.

게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다.

• 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
• 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.

게임은 공이 더 이상 이동할 수 없을 때 끝난다. 이 때, 모든 빈 칸을 공이 방문한 적이 있어야 한다.

아래 그림은 총 10단계 만에 모든 칸을 방문하는 방법이다.

보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

Input

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다. 보드의 상태는 장애물을 나타내는 '*'과 빈 칸을 나타내는 '.'으로 이루어져 있다.

입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.

Output

각 테스트 케이스마다 보드의 모든 빈 칸을 방문하는 최소 이동 횟수를 출력한다. 출력 형식은 예제를 참고한다.

만약, 모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다.

Example

input

5 5
**...
.....
....*
..*..
.....
3 4
****
*...
*..*

output

Case 1: 10
Case 2: 3

Solution & Inpression

색다른 DFS문제 + 입력의 개수가 정해지지 않았기 때문에 EOF 처리로 종료

출력 부분 대소문자와 띄어쓰기를 유의하여야 한다. >> 이부분을 찾느라 1시간이 넘게 걸림.....

Code

언어 : JAVA

메모리 : 20,148 kb

실행시간 : 356 ms

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[][] map;
    // 상 하 좌 우
    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);
        int TC = 0;
        while (sc.hasNext()) {
            N = sc.nextInt();
            M = sc.nextInt();
            map = new int[N][M];
            int blank = -1; // 빈 칸의 개수
            for (int i = 0; i < N; i++) {
                String str = sc.next();
                for (int j = 0; j < M; j++) {
                    if (str.charAt(j) == '*')
                        map[i][j] = 1;
                    else {
                        map[i][j] = 0;
                        blank++;
                    }
                }
            }

            ans = 123456789;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        DFS(i, j, 0, blank);
                        map[i][j] = 0;
                    }
                }
            }
            if (ans == 123456789)
                ans = -1;
            System.out.println("Case " + ++TC + ": " + ans);
        }
    }

    private static void DFS(int i, int j, int cnt, int blank) {
        if (blank == 0 && ans > cnt) {
            ans = cnt;
            return;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nr = i + dr[dir];
            int nc = j + dc[dir];
            if (isRange(nr, nc) && map[nr][nc] == 0) {
                while (isRange(nr, nc) && map[nr][nc] == 0) {
                    map[nr][nc] = 1;
                    blank--;
                    nr += dr[dir];
                    nc += dc[dir];
                }
                nr -= dr[dir];
                nc -= dc[dir];
                DFS(nr, nc, cnt + 1, blank);

                while (nr != i || nc != j) {
                    map[nr][nc] = 0;
                    blank++;
                    nr -= dr[dir];
                    nc -= dc[dir];
                }
            }

        }
    }

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

[BOJ] 16985. Maaaaaaaaaze - Graph/BF/BFS

Problem

제출일 : 2020-02-11

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

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

평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.

대회의 규칙은 아래와 같다.

• 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.

• 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.

• 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.

• 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
• 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.

이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안 된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자.

input

첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.

Output

첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.

Example

input

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

output

16

Solution & Inpression

위 문제는 $5 \times 5$의 판 $5$개가 주어진다.

각각의 판을 회전하고 층을 바꾸어 미로를 구성할 수 있다. 미로를 탈출할때 가장 적은 이동횟수를 출력하면 된다.

각각의 판의 층이 바뀌는 경우의 수는 $5!$ 이며 각 판은 $0,90,180,270$도씩 회전해 4개의 상태를 갖을수 있다,

따라서 생성가능한 미로의 수는
$$
5! \times 4^5 =75,000‬
$$
개의 미로를 생성할 수 있다

생성된 미로를 BFS로 탐색했다 3차원의 x,y,z축에서 각각 +1, -1로 한 칸씩 6방향으로 이동할 수 있다.

순열과 중복순열을 이용해 미로의 경우를 구했고 큐를 이용하여 너비우선 탐색을 구현했다.

Code

언어 : JAVA

메모리 : 279,664 kb

실행시간 : 1,176 ms

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

public class Main {
    static int[][][][] map = new int[5][4][5][5];
    static int[] solData = new int[5], goData = new int[5];
    static boolean[] visit = new boolean[5];
    static int ans;
//상하좌우 아래 위
    static int[] dx = { 0, 0, -1, 1, 0, 0 };
    static int[] dy = { -1, 1, 0, 0, 0, 0 };
    static int[] dz = { 0, 0, 0, 0, 1, -1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[k][0][i][j] = sc.nextInt();
                }
            }
            rotateMap(k);
        }

        ans = Integer.MAX_VALUE;

        solve(0); // 각 판의 회전 정도를 결정

        if (ans == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    private static void solve(int depth) {
        if (depth == 5) {
            go(0); // 판의 순서를 결정
            return;
        }
        for (int i = 0; i < 4; i++) {
            solData[depth] = i;
            solve(depth + 1);
        }
    }

    private static void go(int depth) {
        if (depth == 5) {
            calc();
            return;
        }
        for (int i = 0; i < 5; i++) {
            if (!visit[i]) {
                visit[i] = true;
                goData[depth] = i;
                go(depth + 1);
                visit[i] = false;
            }
        }
    }

    private static void calc() {
        int[][][] copy = new int[5][5][5];
        for (int k = 0; k < 5; k++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    copy[k][i][j] = map[goData[k]][solData[k]][i][j];
                }
            }
        }
        // BFS
        // 입구나 출구가 없는 경우
        if (copy[0][0][0] != 1 || copy[4][4][4] != 1)
            return;

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

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            // 최저값 보다 클 경우 종료
            if (cur[3] >= ans)
                return;
            // 도착 종료
            if (cur[0] == 4 && cur[1] == 4 && cur[2] == 4) {
                if (ans > cur[3])
                    ans = cur[3];
                return;
            }
            for (int dir = 0; dir < 6; dir++) {
                int nz = cur[0] + dz[dir];
                int ny = cur[1] + dy[dir];
                int nx = cur[2] + dx[dir];
                if (isRange(nz, ny, nx) && !visit[nz][ny][nx] && copy[nz][ny][nx] == 1) {
                    q.offer(new int[] { nz, ny, nx, cur[3] + 1 });
                    visit[nz][ny][nx] = true;
                }
            }
        }
    }

    private static boolean isRange(int nz, int ny, int nx) {
        if (0 <= nz && nz < 5 && 0 <= ny && ny < 5 && 0 <= nx && nx < 5)
            return true;
        return false;
    }

    private static void rotateMap(int k) {
        for (int turn = 1; turn < 4; turn++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    map[k][turn][j][4 - i] = map[k][turn - 1][i][j];
                }
            }
        }
    }
}

[BOJ] 14501. 퇴사/15486. 퇴사2 - BF/DP

Problem

제출일 : 2020-02-06

문제 풀이 시간 : 30M / 1H

난이도 : ★☆/★★★☆

---

link 1: https://www.acmicpc.net/problem/14501

link 2: https://www.acmicpc.net/problem/15486

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

Constraints

학생의 수는 1000명이며, 각 학생의 점수는 0점 이상 100점 이하의 값이다.

input

퇴사

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

Output

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

Example

input

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

output

45

Solution & Inpression

퇴사와 퇴사2는 단지 입력되는 값의 범위만 다를 뿐 같은 문제이다.

퇴사는 N의 값이 최대 15이고 퇴사2는 N의 값이 최대 1,500,000이란 차이가 존재한다

문제에서 나올수 잇는 경우의 수는 $2^N$개로 퇴사는 $2^{15}=32,768‬$ 퇴사2에 비해 상대적으로 작은 수이기때문에 완전탐색으로 문제를 해결할 수 있다.

퇴사2는 완전탐색으로 해결할 수 없는 문제로 DP로 문제를 해결해야한다.

아래의 코드를 보면 점화식을 확인 할 수 있다.

DP문제는 아직 너무 어렵다......

Code1

언어 : JAVA

메모리 : 17516 kb

실행시간 : 140 ms

import java.util.Scanner;

public class Main {
    static int N, ans;
    static int[][] data;
    static boolean[] visit;

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

        N = sc.nextInt();
        data = new int[2][N];

        for (int i = 0; i < N; i++) {
            data[0][i] = sc.nextInt();
            data[1][i] = sc.nextInt();
        }
        visit = new boolean[N];
        ans = 0;
        for (int i = 1; i <= N; i++) {
            solve(i, 0, 0);
        }
        System.out.println(ans);
    }

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

    }

    private static void check() {
        boolean[] tmp = new boolean[N];
        for (int i = 0; i < N; i++) {
            if (visit[i]) {
                int end = i + data[0][i];
                if (end > N)
                    return;
                for (int j = i; j < end; j++) {
                    if (tmp[j])
                        return;
                    tmp[j] = true;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (visit[i])
                sum += data[1][i];
        }
        if (ans < sum)
            ans = sum;
    }
}

Code2

언어 : JAVA

메모리 : 370112kb

실행시간 : 2232 ms

import java.util.Scanner;

public class Main {
    public static void main(String[] z) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int[] dp = new int[N + 50];

        for (int i = 1; i <= N; i++) {
            int T = s.nextInt();
            int P = s.nextInt();
            dp[i] = Math.max(dp[i - 1], dp[i]);
            dp[i + T - 1] = Math.max(dp[i + T - 1], dp[i - 1] + P);
        }
        System.out.print(dp[N]);
    }
}

[BOJ] 13023. ABCDE - Graph

Problem

제출일 : 2020-02-03

문제 풀이 시간 : 1H

난이도 : ★★☆

---

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

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

Constraints

학생의 수는 1000명이며, 각 학생의 점수는 0점 이상 100점 이하의 값이다.

input

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

Output

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

Example

input

5 4
0 1
1 2
2 3
3 4

output

1

Solution & Inpression

문제는 일반적인 그래프 탐색문제로 테스트케이스를 맞추는것은 쉽게 풀수 있다. N의 수가 최대 2000으로 문제를 해결할때 완전탐색을 하다 중간에 답을 찾게되면 더 이상 탐색을 하지 않고 멈춰야 한다고 생각을 했다.

하지만 첫 제출때 시간초과가 나 BFS로도 문제를 풀어보고 여러 제약조건들을 추가해 봤지만 시간 초과를 벗어나진 못했다.

관계의 수 M이 작기 때문에 희소행렬로 볼수가 있으므로 인접행렬을 이용하여 문제를 해결하는것보다 인접리스트를 이용하여 문제를 해결하는것이 더 빠른 성능을 낼 수 가 있었다.

Code

언어 : JAVA

메모리 : 22684kb

실행시간 : 436 ms

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    static int N, M, ans;
    static ArrayList<Integer>[] graph;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            graph[s].add(e);
            graph[e].add(s);
        }
        ans = 0;
        visit = new boolean[N];
        for (int i = 0; i < N; i++) {
            DFS(i, 1);
            if (ans == 1)
                break;
        }
        System.out.println(ans);
    }

    private static void DFS(int i, int depth) {
        if (depth == 5 || ans == 1) {
            ans = 1;
            return;
        }
        visit[i] = true;
        for (int j = 0; j < graph[i].size(); j++) {
            if (!visit[graph[i].get(j)]) {
                visit[graph[i].get(j)] = true;
                DFS(graph[i].get(j), depth + 1);
                visit[graph[i].get(j)] = false;
            }
        }
        visit[i] = false;
    }
}

[SWEA] 1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 (D2)

Problem

제출일 : 2020-01-12

문제 풀이 시간 : 20M

난이도 : ★☆

---

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

어느 고등학교에서 실시한 1000명의 수학 성적을 토대로 통계 자료를 만들려고 한다.

이때, 이 학교에서는 최빈수를 이용하여 학생들의 평균 수준을 짐작하는데, 여기서 최빈수는 특정 자료에서 가장 여러 번 나타나는 값을 의미한다.

다음과 같은 수 분포가 있으면,

10, 8, 7, 2, 2, 4, 8, 8, 8, 9, 5, 5, 3

최빈수는 8이 된다.

최빈수를 출력하는 프로그램을 작성하여라 (단, 최빈수가 여러 개 일 때에는 가장 큰 점수를 출력하라).

Constraints

학생의 수는 1000명이며, 각 학생의 점수는 0점 이상 100점 이하의 값이다.

input

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

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호가 주어지고 그 다음 줄부터는 점수가 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

Example

10
1
41 85 72 38 80 69 65 68 96 22 49 67 51 61 63 87 66 24 80 83 71 60 64 52 90 60 49 31 23 99 94 11 25 24 51 15 13 39 67 97 19 76 12 33 99 18 92 35 74 0 95 71 39 33 39 32 37 45 57 71 95 5 71 24 86 8 51 54 74 24 75 70 33 63 29 99 58 94 52 13 35 99 46 57 71 23 17 3 94 48 77 18 83 11 83 25 59 62 2 78 86 7 94 65 80 32 39 84 60 65 72 61 58 84 8 72 12 19 47 49 49 59 71 52 34 22 21 20 92 33 80 39 74 9 28 97 100 93 29 25 4 66 79 81 98 21 91 62 82 4 59 100 34 1 51 80 92 69 77 39 38 97 51 34 35 19 22 1 67 9 90 31 82 11 51 84 78 70 74 42 100 88 53 80 57 62 32 51 48 63 92 46 4 61 31 98 69 52 88 20 68 41 48 79 97 98 56 44 73 3 63 100 87 87 41 79 64 83 63 1 21 72 24 9 75 51 25 53 77 0 52 30 96 93 32 89 70 89 55 71 79 40 10 64 80 30 19 62 67 98 42 8 32 57 27 22 1 38 89 52 74 43 8 2 65 82 20 67 22 43 22 95 16 48 25 6 75 86 96 3 85 43 69 93 4 61 53 81 43 84 20 15 34 22 35 26 28 33 67 19 79 19 45 8 13 51 0 86 68 18 47 82 3 16 80 0 18 39 22 5 26 65 70 21 92 66 65 14 6 46 46 21 32 80 35 86 6 67 29 42 71 14 77 55 3 1 14 38 71 82 41 65 12 5 77 3 67 22 59 40 81 48 63 63 25 45 32 78 83 26 96 18 99 45 56 31 30 45 47 80 1 7 81 18 1 90 15 71 22 69 44 18 31 60 16 93 13 17 44 97 98 51 46 42 22 47 72 97 24 52 55 59 25 100 28 5 14 76 32 41 97 61 32 20 0 2 8 41 52 77 35 22 98 78 92 68 29 82 33 28 16 5 9 21 13 26 39 59 69 10 42 4 13 80 34 42 100 44 32 70 15 32 8 83 10 23 73 8 53 7 21 10 52 14 82 28 24 33 94 59 4 17 73 53 85 31 100 74 74 12 72 38 34 14 22 53 0 30 95 3 52 79 41 36 81 25 24 67 48 95 44 7 96 77 90 48 92 45 78 93 95 38 71 4 83 79 64 89 0 76 81 34 66 1 13 58 4 40 5 24 17 6 65 13 13 76 3 20 8 36 12 60 37 42 53 87 10 65 42 25 47 41 33 71 69 94 24 12 92 11 71 3 82 91 90 20 95 44 76 60 34 95 49 40 89 4 45 27 9 34 82 59 2 20 68 22 29 10 1 23 19 47 16 76 47 49 90 94 10 18 55 69 14 26 59 77 73 8 21 72 1 74 76 51 94 44 24 98 71 77 59 9 12 49 38 72 22 55 35 61 16 48 41 21 67 74 92 4 7 85 34 92 39 96 42 26 1 1 4 64 33 96 62 23 67 76 26 47 32 73 82 30 14 61 21 92 40 4 2 38 76 64 8 14 3 49 71 31 38 86 98 17 15 98 32 55 69 46 61 3 44 67 50 44 76 0 45 23 25 11 82 99 11 39 50 40 21 52 17 60 44 90 44 6 16 38 3 41 43 56 26 24 0 9 90 36 50 13 42 88 87 66 32 28 73 94 52 11 35 47 9 87 37 57 15 56 38 95 6 43 23 30 84 39 88 69 5 34 81 93 86 2 77 10 28 30 97 68 14 12 88 1 100 35 73 30 2 43 11 41 58 82 6 84 71 16 18 67 41 100 92 78 57 7 35 69 56 76 13 93 26 26 38 21 96 7 88 2 60 17 54 95 26 2 0 21 87 11 96 36 83 88 31 24 24 62 14 88 84 39 22 17 84 96 1 78 91 53 9 35 75 87 100 33 80 42 7 20 50 65 81 92 14 45 96 34 6 20 86 51 4 19 70 91 13 0 42 70 43 15 47 14 96 72 41 91 11 72 7 92 12 16 51 13 86 40 50 43 55 26 7 1 70 18 71 99 49 55 94 78 40 59 20 96 34 6 28 85 42 70 62 63 32 34 97 80 49 47 50 73 85 63 20 29 0 19 91 84 58 55 33 4 68 55 12 38 49 9 13 99 4 35 26 5 42 29 98 20 95 77 36 63 41 42 45 81 40 53 60 5 55 9 13 34 6 52 28 35 33 29 21 67 57 61 21 41 95 54 50 19 81 75 67 73 77 47 40 83 16 28
.......

#1 71
#2 76
.......

Solution & Inpression

입력을 받으며 누적합을 구하면 되는 문제로 간단한 D2 문제였지만 문제를 잘 읽어 동점인 경우 어떻게 처리해야하는지를 놓치지 말야햐 한다.

Code

언어 : C++

메모리 : 12,544 kb

실행시간 : 6 ms

#include <iostream>

int score[101];
int T, tmp, ans;

int main(void) {
    scanf("%d", &T);

    for (int tc = 1; tc <= T; tc++)
    {
        scanf("%d", &tmp);
        for (int i = 0; i < 1000; i++)
        {
            scanf("%d", &tmp);
            score[tmp]++;
        }

        tmp = -1, ans = -1;
        for (int i = 0; i < 101; i++)
        {
            if (tmp <= score[i]) {
                tmp = score[i];
                ans = i;
            }

            score[i] = 0;
        }

        printf("#%d %d\n", tc, ans);
    }//end of TC

    return 0;
}

[SWEA] 4006. 고속도로 건설 2

Problem

제출일 : 2019-12-16

문제 풀이 시간 : 25M

난이도 : ★★

---

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxyoNqAiQDFAW4

그러나 비싼 비용의 문제에 부딪혀, 정부는 최소 비용으로 모든 도시 간을 이동할 수 있게 하고 싶어한다.

또한 하나의 제약이 더 있는데, 언덕 등을 깎지 않는 친환경 건설을 위해 어떤 도시끼리는 직접 도로를 이을 수 없다.

친환경 건설을 위해 이을 수 있는 도로의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.

input

첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 8)

각 테스트 케이스의 첫 번째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 50,000)

각 테스트 케이스의 두 번째 줄에 도로 후보의 수 M이 주어진다. (1 ≤ M ≤ 200,000)

각 테스트 케이스의 세 번째 줄부터 M개의 줄에 걸쳐 각 도로 후보의 정보 s, e, c가 주어진다.

s와 e는 도로 후보가 잇는 각 도시의 번호이고, c는 그 도로를 건설하는데 드는 비용이다. (1 ≤ c ≤ 10,000)

항상 모든 도시를 잇는 고속도로를 건설할 수 있는 입력만 주어진다.

Output

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 모든 도시를 잇는 고속도로를 건설하는데 드는 최소 비용을 출력한다.

Example

1
5
8
1 2 4
1 3 9
1 4 21
2 3 8
2 4 17
3 4 16
5 2 20
5 4 30

#1 48

Solution & Inpression

크루스칼 알고리즘을 이용하여 구현하였다.

시간 복잡도를 줄이기 위해 PriorityQueue를 이용하여 가장 적은 비용의 간선을 추출하고 Union-Find알고리즘을 이용 싸이클을 검사했다.

MST 알고리즘은 예전에 확실히 개념을 공부하고 기억하고 있어 쉽게 구현이 가능했다.

Code

언어 : JAVA

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

public class Solution {
    final static int MAX = 50009;
    static PriorityQueue<Edge> pq;
    static int parents[] = new int[MAX];
    static int N, M, ans;

    static class Edge implements Comparable<Edge> {
        int start, end, cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost > o.cost ? 1 : -1;
        }

    }

    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++) {
            N = sc.nextInt();
            M = sc.nextInt();
            pq = new PriorityQueue<>();
            for (int i = 1; i <= M; i++) {
                pq.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
            }

            ans = 0;
            makeSet();

            while (!pq.isEmpty()) {
                Edge e = pq.poll();
                int x = find(e.start);
                int y = find(e.end);
                if (x == y)
                    continue;
                else {
                    ans += e.cost;
                    union(x, y);
                }
            } // end of while
            System.out.println("#" + tc + " " + ans);
        }
    }// end of main

    private static void union(int x, int y) {
        if (x > y)
            parents[x] = parents[y];
        else
            parents[y] = parents[x];
    }

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

    private static void makeSet() {
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }

}