Problem

• 문제 링크

N * M 크기의 미로가 주어졌을 때 (1, 1) 에서 (N, M) 위치로 가기 위한 최소 이동 칸 수를 구하는 문제입니다.

Solution

간단한 BFS 문제입니다.

Dot 클래스를 만들어서 (x, y) 좌표값과 현재까지 이동한 칸의 수 count 를 저장합니다.

BFS 를 돌면서 (N, M) 좌표에 도달했을 때 count 값을 출력하면 됩니다.

Java Code

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] maze = new int[n][m];
        
        for (int i=0; i<n; i++) {
            String s = br.readLine();

            for (int j=0; j<m; j++) {
                maze[i][j] = s.charAt(j) - '0';
            }
        }

        int result = bfs(n, m, maze);
        System.out.println(result);
    }

    static int bfs(int n, int m, int[][] maze) {
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};

        Queue<Dot> q = new LinkedList<>();
        maze[0][0] = 0;
        q.add(new Dot(0, 0, 1));
        
        while (!q.isEmpty()) {
            Dot dot = q.poll();
            
            if (dot.x == n-1 && dot.y == m-1) {
                return dot.count;
            }

            for (int i=0; i<4; i++) {
                int nx = dot.x + dx[i];
                int ny = dot.y + dy[i];

                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (maze[nx][ny] == 1) {
                        maze[nx][ny] = 0;
                        q.add(new Dot(nx, ny, dot.count + 1));
                    }
                }
            }
        }

        return 0;
    }

    static class Dot {
        int x, y, count;

        Dot(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/16940

간단해보였는데 굉장히 많은 시도를 한 문제입니다.

처음에는 연결된 노드 갯수를 기준으로 하였고, 그 다음에는 depth를 기준으로 하였습니다.

그러나 이 문제의 핵심은 결국 어떤 정점은

1) 자신의 부모 정점이 무엇인가

2) 자신의 자식 정점은 몇개가 있는가

위 값들을 전부 아는 상태로 시작해야 합니다.

우선 처음엔 BFS 를 돌면서 부모 노드와 자식 노드의 갯수를 전부 기록해 둡니다.

그리고 주어진 순서를 쭉 순회하면서 현재 노드가 기록했던 부모 노드와 일치하는지 비교하면 됩니다.

parentQueue 라는 변수를 사용하였는데, 부모 노드만을 집어넣는 전용 큐입니다.

childSize 라는 자식 노드의 갯수가 1 이상인 노드들은 전부 parentQueue에 저장되며 자식 노드가 전부 나온 후에야 큐에서 빠져나옵니다.

만약 연속해서 나오는 자식 노드의 갯수가 저장된 childSize와 일치하지 않는다면 불가능한 BFS 라는 뜻이 되겠죠.

Problem

• 문제 링크

괄호만으로 이루어진 문자열이 주어졌을 때 VPS 인지 확인하는 문제입니다.

VPS 란 Valid PS 의 약자로 여는 괄호와 닫는 괄호가 한쌍을 이루는 문자열입니다.

Solution

원래는 스택을 활용하는 문제지만 사실 스택을 사용하지 않아도 됩니다.

문자열은 무조건 ( 또는 ) 만 들어오기 때문에

( 가 들어오면 count++ 

) 가 들어오면 count-- 

처리 해주면 쉽게 구할 수 있습니다.

만약 count 가 음수가 된다면 ( 없이 ) 가 들어왔다는 뜻입니다.

올바른 괄호 문자열이 될 수 없기 때문에 뒤의 문자들은 볼 필요 없이 VPS 가 될 수 없습니다.

문자열을 전부 돌고 난 다음에는 count 가 0 이 되어야 VPS 조건을 만족합니다.

count 가 1 이상이라면 ) 숫자보다 ( 숫자가 더 많다는 뜻이므로 VPS 가 될 수 없습니다.

Java Code

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for (int i=0; i<n; i++) {
            String result = isVPS(br.readLine()) ? "YES\n" : "NO\n";
            sb.append(result);
        }
        
        System.out.println(sb);
    }

    static boolean isVPS(String s) {
        int count = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else {
                if (count == 0) return false;
                count--;
            }
        }

        return count == 0;
    }
}

문제 링크 : https://www.acmicpc.net/problem/10828

스택을 사용하는 문제입니다.

배열을 이용하면 속도는 훨씬 빠르지만 코틀린 스택 연습겸 사용하였습니다.

사실 자바랑 똑같아서 연습이랄 것도 없네요..

코드는 역시 코틀린이 훨씬 더 깔끔합니다.

문제 링크 : https://www.acmicpc.net/problem/1978

소수의 개수를 찾는 문제입니다.

숫자 number는 2 부터 number-1 까지 중에서 나눈 나머지가 0 이 되는 숫자가 존재한다면 소수가 아닙니다.

문제 링크 : https://www.acmicpc.net/problem/15904

간단한 문제입니다.

문장이 주어지면 대문자 U, C, P, C 가 순서대로 들어가 있는지 검사하면 됩니다.

순간적으로 contains 를 쓰면 쉽게 되지 않을까 했는데 

contains를 사용하면 CUPC 처럼 순서가 바뀌어도 "I love UCPC" 를 출력하기 때문에 한번 쭉 돌면서 일일히 비교하는 수밖에 없습니다.

문제 링크 : https://www.acmicpc.net/problem/2811

해석 때문인지는 몰라도 문제를 이해하는데 살짝 어려움을 겪은 문제입니다.

결론을 말하자면 상범이에게 꽃을 주는 날의 최대값을 구하면 됩니다.

이 문제의 핵심은 다음과 같습니다.

1. 상범이의 우울한 정도는 상관없다. 양수, 음수인지만 판단

2. 꽃은 하루에 한개씩만 준다.

3. 꽃을 다 주지 못해도 최대한 준다. 둘째날이 우울한 날이라면 꽃은 첫째날밖에 못준다. 그래도 주자.

4. 3T만큼 꽃을 주는 날은 여러 개의 최장 우울 기간 중 한번이다.

문제를 해결하려면 결국 최장 우울 기간 중 가장 꽃을 많이 줄 수 있는 날이 언제인지 찾는 것이 중요합니다.

이걸 직접 구하는 것보다는 최장 우울 기간 전부 탐색하면서 max값을 구하는 것이 편합니다.

우선 모든 날에 대해서 2T만큼 꽃 주는 날을 구합니다.

그 후에 최장 우울 기간들만 스캔하면서 또다시 3T만큼 카운트합니다.

이 때 2T 구할때 체크했던 날들은 제외해서 중복 체크를 방지합니다.

문제에 있는 예제로 간단하게 설명해보겠습니다.

먼저 상범이의 우울한 날을 구합니다.

그림 1에서 상범이의 최장 우울 기간은 1이고, 최장 우울 기간의 갯수는 3개입니다.

그럼 우선 최장 우울 기간과 관계 없이 모든 우울 기간에 대해서 2T만큼 꽃을 주겠습니다.

우울한 날이 2일이므로 0일과 1일에 꽃을 주어야 합니다.

하지만 보시다시피 0일은 존재하지 않습니다.

이 때, 위에서 언급한 핵심 3번을 보시면 꽃을 다 주지 못해도 최대한 주라는 조건이 있습니다.

그래서 그림 2처럼 체크하면 됩니다.

그리고 두번째로 우울한 날에 대해서 꽃을 줍니다.

그림 3처럼 4일과 5일에 꽃을 줄 수 있습니다.

마지막으로 우울한 날에 대해서 꽃을 줍니다.

8일이 우울한 날이기 때문에 6일과 7일에 꽃을 줍니다.

여기서 헷갈릴 수 있는 요소가 하나 있는데 우울한 날과 관계없이 꽃은 줄 수 있습니다.

따라서 그림 4처럼 2T만큼 모든 우울한 날에 대해서 체크를 하였습니다.

2T를 전부 체크한 시점에서 꽃을 주는 날의 count는 5 입니다.

이제 3T의 최대값을 구해야 합니다.

최장 우울 기간에 해당하는 모든 우울한 날에 대해서 3T를 구합니다.

첫번째 날은 보시다시피 꽃을 더 줄 수 없습니다.

add는 0 입니다.

두번째 우울한 날에 대해서 3T를 구합니다.

우울 기간이 1이기 때문에 꽃을 하루 더 줄 수 있습니다.

이때, 꽃을 줄 수 있는 날은 카운트만 하고 표시는 하지 않습니다.

3T는 모든 여러가지 최장 우울 기간 중 단 한번만 주면 되기 때문입니다.

만약 최장 우울 기간이 1이 아니라 3 정도 되고 3T를 구할때마다 모든 날에 체크를 한다면 뒤에 나오는

최장 우울 기간에는 꽃을 줄  수 있는 날이 없을수도 있고, 그럼 모든 경우의 수를 알 수 없습니다.

아무튼 여기서 add는 1이고 기존의 count 5와 더해서 max 값을 6으로 갱신합니다.

마지막 우울한 날에 대해서 3T를 구합니다.

하지만 이미 3일 전인 5, 6, 7일 전부 꽃을 주기로 되있으므로 꽃을 더 줄 필요가 없습니다.

따라서 추가로 주는 꽃은 없고 add는 0입니다.

최종적으로 꽃을 주는 날은 위와 같고 최대값은 6이 됩니다.

** 코드에서는 뒤에서부터 돌면서 미리 꽃을 주었습니다.

문제 링크 : https://www.acmicpc.net/problem/17284

매우 간단한 구현 문제입니다.

종료 조건이 없기 때문에 StringTokenizer의 st.hasMoreTokens로 토큰이 있는지 검사해도 되지만

저는 어차피 첫번째 줄에만 입력이 들어온다는 조건이 있기 때문에 한줄 받아서 Split(" ")을 사용했습니다.