[Programmers] K번째수 - (Java)

Problem

제출일 : 2020-05-15

문제 풀이 시간 : 5M

난이도 : ★

---

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

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

Solution & Inpression

정렬 문제

Arrays.copyOfRange(original, from, to) 사용하여 문제를 풀어도 되지만 리스트를 사용하여 문제를 해결하였습니다.

Code

언어 : JAVA

package Programmers;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class Level1_K번째수 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new int[] { 1, 5, 2, 6, 3, 7, 4 },
                new int[][] { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 }, }))); // [5,6,3]
    }

    public static int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for (int i = 0; i < commands.length; i++) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int j = commands[i][0] - 1; j < commands[i][1]; j++) {
                list.add(array[j]);
            }
            Collections.sort(list);
            answer[i] = list.get(commands[i][2] - 1);
        }

        return answer;
    }
}

[Programmers] 체육복 - (Java)

Problem

제출일 : 2020-05-15

문제 풀이 시간 : 10M

난이도 : ★

---

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

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

Solution & Inpression

그리디 문제!!

• 잃어버린 사람이 앞사람에게 먼저 물어보고 없으면 뒷사람.

문제 의 조건 중 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 에 유의 하여 문제를 풀면 된다.

Code

언어 : JAVA

package Programmers;

public class Level1_체육복 {
    public static void main(String[] args) {
        System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 1, 3, 5 })); // 5
        System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 3 })); // 4
        System.out.println(solution(3, new int[] { 3 }, new int[] { 1 })); // 2
    }

    public static int solution(int n, int[] lost, int[] reserve) {
        int[] student = new int[n];
        for (int i = 0; i < lost.length; i++) {
            student[lost[i] - 1]--;
        }
        for (int i = 0; i < reserve.length; i++) {
            student[reserve[i] - 1]++;
        }

        int answer = n;
        for (int i = 0; i < student.length; i++) {
            if (student[i] == -1) {
                if (i - 1 >= 0 && student[i - 1] == 1) {
                    student[i]++;
                    student[i - 1]--;
                } else if (i + 1 < student.length && student[i + 1] == 1) {
                    student[i]++;
                    student[i + 1]--;
                } else
                    answer--;
            }
        }
        return answer;
    }
}

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