[BOJ] 15661. 링크와 스타트 - (Java)

Problem

제출일 : 2020-05-06

문제 풀이 시간 : 15M

난이도 : ★★

---

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

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

Input

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

Output

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

Example

input

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

output

0

Solution & Inpression

평이한 완전탐색문제

팀을 나누고 팀별 능력치를 계산하여 갱신하는 방법으로 문제를 해결

Code

언어 : JAVA

메모리 : 16888 kb

실행 시간 : 1092 ms

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

public class Gold5_15661_링크와스타트 {
    static int N, ans;
    static int[][] graph;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        ans = Integer.MAX_VALUE;
        visit = new boolean[N];
        solve(0, 0);
        System.out.println(ans);
    }

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

    private static void check() {
        int start = 0;
        int link = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (visit[i] != visit[j])
                    continue;
                if (visit[i])
                    start += graph[i][j] + graph[j][i];
                else
                    link += graph[i][j] + graph[j][i];
            }
        }
        int tmp = Math.abs(start - link);
        if (tmp < ans)
            ans = tmp;
    }
}

[BOJ] 3197. 백조의 호수 - (Java)

Problem

제출일 : 2020-05-06

문제 풀이 시간 : 3H

난이도 : ★★★★

---

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

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.

Input

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

각 R줄 동안 C만큼의 문자열이 주어진다.

'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

Output

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

Example

input

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

output

2

Solution & Inpression

시간초과로 문제 해결이 어려웠던 문제이다.

단순히 BFS로 문제를 구현하는 것 이상의 아이디어가 필요했다.

어려웠던 문제로 블로그의 글을 참고해 문제를 해결하였습니다.

Code

언어 : JAVA

메모리 : 215728 kb

실행 시간 : 1012 ms

package BOJ.DFS_BFS;
import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Gold1_3197_백조의호수 {
    static int R, C;
    static char[][] map;
    static Point[] swan;

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

    static Queue<int[]> swanQ;
    static Queue<int[]> waterQ;

    static boolean[][] visit_swan;

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

        map = new char[R][C];
        swan = new Point[2];

        swanQ = new LinkedList<>();
        visit_swan = new boolean[R][C];

        waterQ = new LinkedList<>();

        // 데이터 입력
        int index = 0;
        for (int i = 0; i < R; ++i) {
            String line = sc.next();
            for (int j = 0; j < C; ++j) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'L') {
                    map[i][j] = '.';
                    swan[index++] = new Point(i, j);
                }
                if (map[i][j] == '.') {
                    waterQ.add(new int[] { i, j });
                }
            }
        }

        // 출발점이 되는 백조
        swanQ.add(new int[] { swan[0].x, swan[0].y });
        visit_swan[swan[0].x][swan[0].y] = true;

        int day = 0;
        while (true) {
            if (move_swan())
                break;
            melt();
            day++;
        }

        System.out.println(day);
    }

    private static boolean move_swan() {
        Queue<int[]> nextQ = new LinkedList<>();
        while (!swanQ.isEmpty()) {
            int[] now = swanQ.poll();

            if (now[0] == swan[1].x && now[1] == swan[1].y) {
                return true;
            }

            for (int k = 0; k < 4; ++k) {
                int nr = now[0] + dr[k];
                int nc = now[1] + dc[k];

                if (!isRange(nr, nc) || visit_swan[nr][nc])
                    continue;
                visit_swan[nr][nc] = true;
                if (map[nr][nc] == '.') {
                    swanQ.add(new int[] { nr, nc });
                }
                // 다음날 얼음이 녹아 백조가 지나 갈 수 있음.
                else if (map[nr][nc] == 'X') {
                    nextQ.add(new int[] { nr, nc });
                }
            }
        }
        // q를 다음날 탐색할 지역이 담긴 nextQ로 바꾼다.
        swanQ = nextQ;
        return false;
    }

    private static void melt() {
        // 얼음을 녹인다.
        int size = waterQ.size();
        for (int i = 0; i < size; ++i) {
            int[] now = waterQ.poll();

            for (int k = 0; k < 4; ++k) {
                int nr = now[0] + dr[k];
                int nc = now[1] + dc[k];

                if (isRange(nr, nc) && map[nr][nc] == 'X') {
                    map[nr][nc] = '.';
                    waterQ.add(new int[] { nr, nc });
                }
            }
        }
    }

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

Reference

https://velog.io/@hyeon930/BOJ-3197-%EB%B0%B1%EC%A1%B0%EC%9D%98-%ED%98%B8%EC%88%98-Java

[BOJ] 17472. 다리만들기2 (Java)

Problem

제출일 : 2020-04-14

문제 풀이 시간 : 2H 30M

난이도 : ★★★☆

---

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

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다.총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2)다리 B: 3과 4를 연결 (길이 3)다리 C: 2와 5를 연결 (길이 5)다리 D: 1과 2를 연결 (길이 2)총 길이: 12

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

Constraints

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

Input

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

Output

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

각 줄은 “#x”로 시작하고, 공백을 하나 둔 후 정답을 출력한다. (x는 테스트 케이스의 번호이며, 1번부터 시작한다.)

출력해야 할 정답은 M시간 후 남아 있는 미생물 수의 총 합이다.

Example

input

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

output

9

Solution & Inpression

문제 풀이 순서

1. 입력 받은 map의 섬의 개수를 파악하며 섬에 번호를 붙여준다 (DFS)
2. 각 섬에서 출발하여 도착 가능한 섬에 건설할수 있는 최소비용을 찾는다. (BFS)
3. 모든 섬을 연결하는 다리 길이의 최솟값을 구한다(MST:최소신장트리)

이 문제는 완전탐색, 너비우선탐색, 깊이우선탐색, 그래프이론, 최소신장트리를 이용하여 구현하는 문제로 문제의 난이도가 높다.

Code

언어 : JAVA

메모리 : 14512 kb

실행시간 : 116ms

package BOJ.Graph;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


public class Gold3_17472_다리만들기2 {
    static int N, M;
    static int[][] map;

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

    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = 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();
                if (map[i][j] == 1)
                    map[i][j] = -1;
            }
        }

        // 맵 라밸링 맵의개수 파악
        int island = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1) {
                    DFS(i, j, island++);
                }
            }
        }

        // 간선의 비용 구하기
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        for (int i = 1; i < island; i++) {
            for (int j = i + 1; j < island; j++) {
                int cost = getBridge(i, j);
                if (cost != 0)
                    pq.add(new int[] { i, j, cost });
            }
        }

        // makeSet
        parent = new int[island];
        for (int i = 1; i < island; i++) {
            parent[i] = i;
        }

        int ans = 0;
        // 다리선택 MST
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            int x = find(now[0]);
            int y = find(now[1]);
            if (x != y) {
                union(now[0], now[1]);
                ans += now[2];
            }
        }

        // 결과
        boolean flag = true;
        for (int i = 1; i < island; i++) {
            if (find(i) != 1) {
                flag = false;
                break;
            }
        }
        System.out.println(flag ? ans : -1);
    }

    private static void union(int i, int j) {
        int x = find(i);
        int y = find(j);

        if (x > y)
            parent[x] = y;
        else
            parent[y] = x;
    }

    private static int find(int i) {
        if (i == parent[i])
            return i;
        return parent[i] = find(parent[i]);
    }

    private static int getBridge(int start, int end) {
        boolean[][][] visit = new boolean[N][M][4];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != start)
                    continue;
                for (int k = 0; k < dr.length; k++) {
                    int r = i + dr[k];
                    int c = j + dc[k];
                    if (!isRange(r, c) || map[r][c] != 0)
                        continue;
                    q.add(new int[] { r, c, 0, k });
                    visit[r][c][k] = true;
                }
            }
        }

        int ret = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            if (map[now[0]][now[1]] == end) {
                if (now[2] == 1)
                    continue;
                ret = now[2];
                break;
            }
            int nr = now[0] + dr[now[3]];
            int nc = now[1] + dc[now[3]];

            if (isRange(nr, nc) && !visit[nr][nc][now[3]]
                    && (map[nr][nc] == 0 || map[nr][nc] == end)) {
                visit[nr][nc][now[3]] = true;
                q.add(new int[] { nr, nc, now[2] + 1, now[3] });
            }
        }

        return ret;
    }

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

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

[BOJ] 1922. 네트워크연결 - (Java)

Problem

제출일 : 2020-04-08

문제 풀이 시간 : 30M

난이도 : ★★★

---

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

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

Input

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

Output

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

Example

input

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

output

23

Hint

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

Solution & Inpression

유니온 파인드를 이용한 최소스패닝트리 알고리즘.

Code

언어 : JAVA

메모리 : 225564 kb

실행 시간 : 1100 ms

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

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

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

        N = sc.nextInt();
        M = sc.nextInt();
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        for (int i = 0; i < M; i++) {
            pq.offer(new int[] { sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt() });
        }

        parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] now = pq.poll();

            int a = find(now[0]);
            int b = find(now[1]);

            if (a == b)
                continue;

            union(a, b);
            ans += now[2];
        }
        System.out.println(ans);
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y)
                parent[y] = x;
            else
                parent[x] = y;
        }
    }

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

[BOJ] 2573. 빙산 - (Java)

Problem

제출일 : 2020-04-08

문제 풀이 시간 : 1H 30M

난이도 : ★★★

---

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

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

Input

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

Output

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

Example

input

5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

output

2

Solution & Inpression

빙산이 녹는 조건을 잘 읽자......

Code

언어 : JAVA

메모리 : 255480 kb

실행 시간 : 1092 ms

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

public class Main {
    static int N, M;
    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();
        M = 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();
            }
        }
        int ans = 0;
        while (true) {
            ans++;

            int[][] mel = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0) {
                        int m = 0;
                        for (int k = 0; k < dr.length; k++) {
                            int nr = i + dr[k];
                            int nc = j + dc[k];
                            if (isRange(nr, nc) && map[nr][nc] == 0)
                                m++;
                        }
                        mel[i][j] = m;
                    }
                }
            }

            Queue<int[]> q = new LinkedList<>();
            boolean[][] visit = new boolean[N][M];
            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    map[i][j] -= mel[i][j];
                    if (map[i][j] < 0)
                        map[i][j] = 0;
                    else if (map[i][j] > 0) {
                        count++;
                        if (q.isEmpty()) {
                            q.offer(new int[] { i, j });
                            visit[i][j] = true;
                        }
                    }
                }
            }
            if (count == 0) {
                System.out.println(0);
                return;
            }
            int size = 1;
            while (!q.isEmpty()) {
                int[] now = q.poll();
                for (int k = 0; k < dr.length; k++) {
                    int nr = now[0] + dr[k];
                    int nc = now[1] + dc[k];
                    if (isRange(nr, nc) && map[nr][nc] > 0 && !visit[nr][nc]) {
                        visit[nr][nc] = true;
                        q.offer(new int[] { nr, nc });
                        size++;
                    }
                }
            }

            if (size != count) {
                System.out.println(ans);
                return;
            }
        }
    }

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

[BOJ] 10816. 숫자 카드 2 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 30M

난이도 : ★★★

---

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

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

Input

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

Output

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

Example

input

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

output

3 0 0 1 2 0 0 2

Solution & Inpression

upper_bound, lower_bound 연습문제

자바는 위 함수가 없기에 구현하여 문제를 해결하여야 합니다.

Code

언어 : JAVA

메모리 : 297116 kb

실행 시간 : 2164 ms

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

public class Main {
    static int N;
    static int card[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        card = new int[N];
        for (int i = 0; i < N; i++) {
            card[i] = sc.nextInt();
        }
        Arrays.sort(card);
        int M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            sb.append(check(sc.nextInt())).append(" ");
        }
        System.out.println(sb);
    }

    private static int check(int x) {
        int low = lower(x);
        int high = upper(x);
        return high - low + 1;
    }

    private static int upper(int x) {
        int s = 0, e = N;
        while (s < e) {
            int m = (s + e) >> 1;
            if (card[m] == x) {
                s = m + 1;
            } else if (card[m] > x) {
                e = m;
            } else
                s = m + 1;
        }
        return e;
    }

    private static int lower(int x) {
        int s = 0, e = N;
        while (s < e) {
            int m = (s + e) >> 1;
            if (card[m] == x) {
                e = m;
            } else if (card[m] > x) {
                e = m;
            } else
                s = m + 1;
        }
        return s + 1;
    }
}

[BOJ] 9012. 괄호 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 15M

난이도 : ★★

---

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

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

Input

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

Output

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

Example

input

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

output

NO
NO
YES
NO
YES
NO

Solution & Inpression

스택을 이용하여 해결

여는 괄호를 만났을 때 스택에 담고 닫히는 괄호를 만났을 때 스택의 크기를 확인하여 검사

최종적으로 스택이 비어있지 않다면 VPS가 아님.

Code

언어 : JAVA

메모리 : 14700 kb

실행 시간 : 124 ms

import java.util.LinkedList;
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();
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < N; tc++) {
            Stack<Character> stack = new Stack<>();

            String input = sc.next();
            boolean flag = true;
            for (int i = 0; i < input.length(); i++) {
                char now = input.charAt(i);
                if (now == '(')
                    stack.push(now);
                else if (now == ')') {
                    if (stack.size() > 0)
                        stack.pop();
                    else
                        flag = false;
                }
                if (!flag)
                    break;
            }
            if (stack.size() > 0)
                flag = false;
            sb.append(flag ? "YES\n" : "NO\n");
        } // end of TC
        System.out.println(sb);
    }
}

[BOJ] 2164. 카드2 - (Java)

Problem

제출일 : 2020-04-02

문제 풀이 시간 : 10M

난이도 : ★★

---

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

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

Input

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

Output

첫째 줄에 남게 되는 카드의 번호를 출력한다.

Example

input

6

output

4

Solution & Inpression

삽입삭제가 빈번하게 일어나기 때문에 LinkedList를 사용

카드가 한장이 남을때 까지 반복하여 마지막 카드를 출력

Code

언어 : JAVA

메모리 : 45892kb

실행 시간 : 188ms

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        LinkedList<Integer> cards = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            cards.add(i);
        }
        while (cards.size() != 1) {
            cards.remove(0);
            cards.add(cards.get(0));
            cards.remove(0);
        }

        System.out.println(cards.get(0));
    }
}