[Programmers] 모의고사 - (Java)

Problem

제출일 : 2020-05-11

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42840

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

Solution & Inpression

간단한 문제로 다음의 단계로 문제를 해결하였습니다.

1. 각각의 사람들이 문제를 찍는 패턴을 배열에 저장한다.
2. %연산자를 이용하여 각각의 사람들이 맞춘 문제의 수를 카운팅한다.
3. 맞춘 문제의 수의 최대값을 구한다.
4. ArrayList를 이용하여 맞춘 문제의 수가 최대값과 같은 인원을 구한다.
5. list의 값을 배열에 저장하여 리턴한다.

Code

언어 : JAVA

package Programmers;

import java.util.ArrayList;
import java.util.Arrays;

public class Level1_모의고사 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new int[] { 1, 2, 3, 4, 5 }))); // 1
        System.out.println(Arrays.toString(solution(new int[] { 1, 3, 2, 4, 2 }))); // 1, 2, 3
    }

    public static int[] solution(int[] answers) {
        int[] p1 = { 1, 2, 3, 4, 5 };
        int[] p2 = { 2, 1, 2, 3, 2, 4, 2, 5 };
        int[] p3 = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };
        int[] cnt = new int[3];
        for (int i = 0; i < answers.length; i++) {
            int now = answers[i];
            if (p1[i % p1.length] == now)
                cnt[0]++;
            if (p2[i % p2.length] == now)
                cnt[1]++;
            if (p3[i % p3.length] == now)
                cnt[2]++;
        }
        int max = Math.max(Math.max(cnt[0], cnt[1]), cnt[2]);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == max)
                list.add(i + 1);
        }
        int[] answer = new int[list.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}

[Programmers] 완주하지 못한 선수 - (Java)

Problem

제출일 : 2020-05-11

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42576

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

Solution & Inpression

HashMap을 사용하여 문제를 해결하였습니다.

Code

언어 : JAVA

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        System.out.println(
                solution(new String[] { "leo", "kiki", "eden" }, new String[] { "eden", "kiki" }));// leo
        System.out.println(solution(new String[] { "marina", "josipa", "nikola", "vinko", "filipa" },
                new String[] { "josipa", "filipa", "marina", "nikola" }));// vinko
        System.out.println(solution(new String[] { "mislav", "stanko", "mislav", "ana" },
                new String[] { "stanko", "ana", "mislav" }));// mislav
    }

    public static String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        for (String player : participant)
            map.put(player, map.getOrDefault(player, 0) + 1);
        for (String player : completion)
            map.put(player, map.get(player) - 1);

        String answer = "";
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                answer = key;
            }
        }
        return answer;
    }
}

[Programmers] 크레인 인형뽑기 게임 - (Java)

Problem

제출일 : 2020-05-11

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://programmers.co.kr/learn/courses/30/lessons/64061

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

Solution & Inpression

2019 카카오 개발자 겨울 인턴십 문제

문제에 주어진 대로 구현하는 문제로 스택을 이용하여 문제를 해결하였습니다.

먼저 보드에 들어있는 인형을 해당하는 열의 리스트에 담아 두어 크레인의 위치에 따라 가장 첫번째 인형을 뽑을 수 있게 담아 두었고 인형을 뽑은뒤 스택에 담는데 이때 스택이 비어있지 않고 Top의 인형이 지금 뽑은 인형과 같은 인형일때 answer를 2 증가시킨뒤 Top의 값을 pop하는 방법을 사용하였습니다.

Code

언어 : JAVA

package Programmers;
import java.util.LinkedList;
import java.util.Stack;

public class Level1_크레인인형뽑기게임
 {
    public static void main(String[] args) {
        System.out.println(solution(new int[][] { { 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 3 }, { 0, 2, 5, 0, 1 },
                { 4, 2, 4, 4, 2 }, { 3, 5, 1, 3, 1 } }, new int[] { 1, 5, 3, 5, 1, 2, 1, 4 }));
    }

    public static int solution(int[][] board, int[] moves) {
        int N = board.length;

        LinkedList<Integer>[] list = new LinkedList[N];
        for (int i = 0; i < list.length; i++) {
            list[i] = new LinkedList<>();
        }
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < N; i++) {
                if (board[i][j] != 0)
                    list[j].add(board[i][j]);
            }
        }

        Stack<Integer> st = new Stack<>();
        int answer = 0;
        for (int m : moves) {
            if (list[m - 1].size() == 0)
                continue;

            int now = list[m - 1].pollFirst();
            if (!st.isEmpty() && st.peek() == now) {
                st.pop();
                answer += 2;
            } else
                st.push(now);
        }
        return answer;
    }
}

[BOJ] 7569. 토마토- (Java)

Problem

제출일 : 2020-05-07

문제 풀이 시간 : 20M

난이도 : ★★

---

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

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

Input

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

Output

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

Example

input

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

output

-1

Solution & Inpression

그래프 탐색문제

3차원 맵으로 상,하,좌,우,위,아래 6방향을 검사하여야 한다.

-1이 나오는 경우 아직 익지 않은 토마토가 있을경우로 BFS 탐색이 끝난뒤 맵을 탐색하여 0을 찾는 방법으로 진행하였다. 미리 개수를 새어 놓았다면 탐색을 하지 않고 바로 확인이 가능할 것 이라 생각한다.

Code

언어 : JAVA

메모리 : 293700 kb

실행 시간 : 1424 ms

package BOJ.DFS_BFS;

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

public class Silver1_7569_토마토 {
    static int N, M, H;
    static int[][][] map;

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

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

        map = new int[H][N][M];
        Queue<int[]> q = new LinkedList<>();

        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    // 1은 익은 토마토, 0 은 익지 않은 토마토, -1은 빈 칸
                    map[k][i][j] = sc.nextInt();
                    if (map[k][i][j] == 1)
                        q.add(new int[] { k, i, j });
                }
            }
        }
        int ans = -1;
        while (!q.isEmpty()) {
            int size = q.size();
            ans++;
            for (int s = 0; s < size; s++) {
                int[] now = q.poll();
                for (int k = 0; k < dir.length; k++) {
                    int nh = now[0] + dir[k][0];
                    int nr = now[1] + dir[k][1];
                    int nc = now[2] + dir[k][2];
                    if (isRange(nh, nr, nc) && map[nh][nr][nc] == 0) {
                        map[nh][nr][nc] = 1;
                        q.add(new int[] { nh, nr, nc });
                    }
                }
            }
        }
        boolean flag = true;
        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[k][i][j] == 0) {
                        flag = false;
                        break;
                    }
                }
            }
        }
        System.out.println(flag ? ans : -1);

    }

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

[BOJ] 2644. 촌수계산 - (Java)

Problem

제출일 : 2020-05-07

문제 풀이 시간 : 15M

난이도 : ★★

---

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

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

Input

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

Output

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

Example

input

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

output

3

Solution & Inpression

기본적인 그래프 탐색문제

Code

언어 : JAVA

메모리 : 14396 kb

실행 시간 : 112 ms

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

public class Silver2_2664_촌수계산 {
    static int N;
    static boolean[][] graph;

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

        graph = new boolean[N][N];
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt() - 1;
            int e = sc.nextInt() - 1;
            graph[s][e] = graph[e][s] = true;
        }
        System.out.println(BFS(start, end));
    }

    private static int BFS(int start, int end) {
        boolean[] visit = new boolean[N];
        Queue<Integer> q = new LinkedList<>();
        visit[start] = true;
        q.add(start);

        int ans = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int now = q.poll();
                if (now == end)
                    return ans;
                for (int i = 0; i < N; i++) {
                    if (graph[now][i] && !visit[i]) {
                        visit[i] = true;
                        q.add(i);
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}

[BOJ] 3190. 뱀 - (Java)

Problem

제출일 : 2020-05-06

문제 풀이 시간 : 1H

난이도 : ★★

---

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

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

Input

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

Output

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

Example

input

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

output

9

Solution & Inpression

시뮬레이션 문제

1. 일단 현위치에서 이동할 방향으로 머리를 1칸 이동한다.
2. 이동한 자리가 사과가 아니라면 꼬리를 0으로
3. 현재 경과시간에 방향전환 값이 있다면 방향을 바꾼다.

문제를 천천히 읽어보고 이를 그대로 구현하면 되는 평이한 문제다.

Code

언어 : JAVA

메모리 : 15248 kb

실행 시간 : 140 ms

package BOJ.Simulation;

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

public class Gold5_3190_뱀 {
    static int N, K, L;
    static int[][] map;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 보드의 크기 N
        K = sc.nextInt(); // 사과의 개수 K

        map = new int[N][N];
        for (int i = 0; i < K; i++) {
            map[sc.nextInt() - 1][sc.nextInt() - 1] = 1;
        }

        L = sc.nextInt(); // 뱀의 방향 변환 횟수 L
        LinkedList<int[]> cmd = new LinkedList<>();

        for (int i = 0; i < L; i++) {
            int t = sc.nextInt();
            int d = sc.next().charAt(0) == 'L' ? -1 : 1;
            cmd.add(new int[] { t, d });
        }

        int time = 0;
        int dir = 1;
        LinkedList<int[]> snake = new LinkedList<>();
        snake.add(new int[] { 0, 0 });
        while (true) {
            time++;
            int[] head = snake.getLast();

            int[] tail = snake.getFirst();
            int nr = head[0] + dr[dir];
            int nc = head[1] + dc[dir];

            if (!isRange(nr, nc))
                break;

            if (map[nr][nc] == 0) {
                snake.add(new int[] { nr, nc });
                map[nr][nc] = 2;
                map[tail[0]][tail[1]] = 0;
                snake.remove(0);
            } else if (map[nr][nc] == 1) {
                snake.add(new int[] { nr, nc });
                map[nr][nc] = 2;
            } else
                break;

            if (!cmd.isEmpty() && time == cmd.getFirst()[0]) {
                if (cmd.getFirst()[1] == 1) { // 오른쪽
                    if (dir == 3)
                        dir = 0;
                    else
                        dir++;
                } else { // 왼쪽
                    if (dir == 0)
                        dir = 3;
                    else
                        dir--;
                }
                cmd.remove(0);
            }
        }
        System.out.println(time);

    }

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

[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