백준 - 테트로미노 14500, 문자열 폭발 9935

백준에서 오토에버 코테 준비를 하다가 재밌는 문제를 발견해서 가져왔다. 사실 알고리즘은 전부 알고 있는 것들인데 문제로 만나게 되었을 때 정말 새롭게 다가오는 문제여서 기록을 남겨보려고 한다.

 

백준 - 테트로미노 14500, 문자열 폭발 9935

 

목차

 

1. 테트로미노

2. 테트로미노 코드

3. 문자열 폭발

4. 문자열 폭발 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

테트로미노

• 처음에는 이 도형들을 어떻게 다 탐색을 할 수 있을까? 심지어 회전도 해야하는데 어떻게 할 수 있을까 고민을 했었는데, 다른 블로그를 참고하자마자 바로 탄성을 터트렸다.
• 원리는 아주 단순한데 ㅗ 모양 블록을 제외하고는 전부 한 점에서 깊이가 4인 DFS를 돌렸을 때 얻을 수 있는 모양이었다.
• 그림으로 나타내면 아래와 같다.

1자 블럭

정사각형 블록

두번 꺾인 블록

긴 ㄴ자 블록

• 이처럼 회전하는 경우를 포함해서 모두 고려할 수 있다.
• 그렇다면 ㅗ 모양 블록은 어떻게 고려할 수 있을까?
• 기본적으로 DFS의 경우 탐색을 시작할 점이 다음 지점으로 이동한다.
• 그렇지만 ㅗ 블록의 경우 2번째 점을 기준으로 분기하는 점을 고려해 다음 탐색 지점을 다음 갈 곳으로 옮기는 것이 아니라 현재 지점으로 설정하면 된다.
• DFS 함수 내에서 if (depth == 2)인 경우를 살펴보면, 조건문 내부에서 다시 DFS를 호출하지만, 일반적인 경우와 다르게 현재 지점을 기준으로 다시 다른 점을 탐색하는 것을 알 수 있다.
• 아래는 실제 코드이다.

테트로미노 코드

import java.util.*;
import java.io.*;
public class Main {
    static Stack<String> st = new Stack<>();
    static int answer = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    static boolean isInTheMap(int x, int y, int limitX, int limitY) {
        if (x > -1 && y > -1 && x < limitX && y < limitY)
            return true;
        return false;
    }

    public static void dfs(int x, int y, int sum, int depth, int[][] visited, int[][] maps) {
        if (depth == 4) {
            answer = Math.max(answer, sum);
        } else {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (isInTheMap(nx, ny, maps.length, maps[0].length) && visited[nx][ny] == -1) {
                    if (depth == 2) {
                        visited[nx][ny] = 1;
                        dfs(x, y, sum + maps[nx][ny], depth + 1, visited, maps);
                        visited[nx][ny] = -1;
                    }
                    visited[nx][ny] = 1;
                    dfs(nx, ny, sum + maps[nx][ny], depth + 1, visited, maps);
                    visited[nx][ny] = -1;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] s = bf.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);

        int[][] maps = new int[N][M];
        for (int i = 0; i < N; i++) {
            String[] temp = bf.readLine().split(" ");
            for (int j = 0; j < M; j++)
                maps[i][j] = Integer.parseInt(temp[j]);
        }

        int[][] visited = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(visited[i], -1);
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = 1;
                dfs(i, j, maps[i][j], 1, visited, maps);
                visited[i][j] = -1;
            }
        }

        System.out.println(answer);
    }
}

문자열 폭발

• 처음에는 replace를 사용해서 풀었는데, 메모리 초과가 났다.
• 아무래도 새로운 String이 계속 생성되서 그럴 것이라고 생각한다.
• 그래서 조금 찾아보니 스택을 이용해서 쉽게 풀 수 있었다.
• 전부 다 비교하더라도 경우의 수가 얼마 되지 않기 때문에 시간 복잡도도 문제가 없는 것 같다.
• 아이디어는 정말 간단한데, 스택에 글자를 하나 넣고 스택의 끝부터 폭발 문자열 길이만큼을 가져와 폭발하는 문자열인지 확인한다.
• 만약 폭발 문자열과 일치해 폭발해야 된다면, 스택에서 폭발 문자열 길이만큼 글자를 pop()하면 된다.
• 이런 식으로 모든 문자열을 담는 과정이 마무리 되었을 때, 스택에 남아있는 글자를 출력하면 된다.
• 이때, 주의할 점이 하나 있다.
• 마지막에 문자열을 출력할 때, System.out.print() 문을 이용해서 스택의 값을 하나하나 출력하게 되면 시간 초과가 뜬다.
• 따라서 시간 초과를 방지하려면 StringBuilder를 사용해서 문자열을 완성시키고 한번에 출력하는 식으로 시간을 아껴야 한다.

문자열 폭발 코드

import java.util.*;
import java.io.*;
public class Main {
    static Stack<String> st = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] s = bf.readLine().strip().split("");
        String[] target = bf.readLine().strip().split("");
        for (int i = 0; i < s.length; i++) {
            st.push(s[i]);
            if (st.size() >= target.length) {
                int chk = 1;
                for (int j = target.length - 1; j >= 0; j--) {
                    if (!st.get(st.size() - 1 - (target.length-1-j)).equals(target[j])) {
                        chk = 0;
                        break;
                    }
                }
                if (chk == 1) {
                    for (int j = 0; j < target.length; j++)
                        st.pop();
                }
            }
        }

        if (st.isEmpty())
            System.out.println("FRULA");
        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < st.size(); i++)
                sb.append(st.get(i));
            System.out.println(sb);
        }
    }
}