[JAVA] 백준 12919 완전 탐색

 

 

 

12919번: A와 B 2

문제

문자열 S가 주어졌을 때 2가지 연산을 진행하여 주어진 T를 만족하는 문자열을 만들 수 있는지 여부를 검사하여 출력하시오.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public static int answer = 0;

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

        String S = br.readLine();
        String T = br.readLine();

        DFS(S, T);
        System.out.println(answer);
    }

    private static void DFS(String s, String t){
        if (s.length() >= t.length() || answer == 1){
            if(s.equals(t)) answer = 1;
            return;
        }

        DFS(operation1(s), t);
        DFS(operation2(s), t);
    }

    private static void BFS(String s, String t){
        Queue<String> q = new LinkedList<>();
        q.add(s);
        while (!q.isEmpty()){
            String now = q.poll();
            if(now.equals(t)) {
                answer = 1;
                break;
            }
            if(now.length() > t.length()){
                break;
            }
            q.add(operation1(now));
            q.add(operation2(now));
        }
    }

    private static String operation1(String s){
        return s + "A";
    }

    private static String operation2(String s){
        StringBuffer sb = new StringBuffer(s + "B");
        return sb.reverse().toString();
    }
}

처음에는 DFS로 구상하여 만들어서 테스트했지만 시간이 너무 많이걸렸다.

따라서 BFS로 구상했지만 메모리가 초과했다.

서칭을 통해 알아낸 접근법

서칭을 통해 알아본 결과 S → T로 만드는 경우의 수는 모든 경우의 수를 체크해주어야 했지만 T → S로 만드는 경우의 수는 비교적 매우 작다는 것을 알게되었다.

따라서 그에 맞춰서 구현해주었다.

DFS

private static void DFS(String s, String t){
                // answer가 1이거나 길이가 같아지면 종료
        if (s.length() == t.length() || answer == 1){
                        // s와 t가 같다면 정답 체크
            if(s.equals(t)) answer = 1;
            return;
        }

                // T의 끝이 A로 끝난다면 T 뒤의 A를 제거해주는 연산을 진행하고 다시 탐색
        if(t.endsWith("A")) DFS(s, operation1(t));
                // T의 시작이 B로 시작한다면 T를 reverse하고 뒤의 B를 제거해주는 연산을 진행하고 다시 탐색
        if(t.startsWith("B")) DFS(s, operation2(t));
    }

2가지의 경우를 보고 연산을 진행했다.

1. T의 문자열 가장 마지막이 A로 끝난다면 T의 마지막 A를 제거하고 재귀적으로 탐색을 진행한다.
2. T의 문자열 가장 첫 번째가 B로 시작한다면 T를 뒤집고 B를 제거하고 재귀적으로 탐색을 진행한다.

만약 S가 되는 경우의 수를 발견했거나 s와 t의 길이가 같다면 탐색을 종료하고, s와 t가 동등하다면 answer를 체크해준다.

Operation

// T에서 뒤의 A를 제거하는 연산
    private static String operation1(String t){
        return t.substring(0, t.length()-1);
    }

    // T를 뒤집고 뒤의 B를 제거하는 연산
    private static String operation2(String t){
        return new StringBuilder(t).reverse().substring(0, t.length()-1);
    }

Operation은 문제에서 주어진 두 가지 연산을 구현해주었다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public static int answer = 0;

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

        String S = br.readLine();
        String T = br.readLine();

        DFS(S, T);
        System.out.println(answer);
    }

    private static void DFS(String s, String t){
                // answer가 1이거나 길이가 같아지면 종료
        if (s.length() == t.length() || answer == 1){
                        // s와 t가 같다면 정답 체크
            if(s.equals(t)) answer = 1;
            return;
        }

                // T의 끝이 A로 끝난다면 T 뒤의 A를 제거해주는 연산을 진행하고 다시 탐색
        if(t.endsWith("A")) DFS(s, operation1(t));
                // T의 시작이 B로 시작한다면 T를 reverse하고 뒤의 B를 제거해주는 연산을 진행하고 다시 탐색
        if(t.startsWith("B")) DFS(s, operation2(t));
    }

    // T에서 뒤의 A를 제거하는 연산
    private static String operation1(String t){
        return t.substring(0, t.length()-1);
    }

    // T를 뒤집고 뒤의 B를 제거하는 연산
    private static String operation2(String t){
        return new StringBuilder(t).reverse().substring(0, t.length()-1);
    }
}

결과

단순하게 문제에서 주어진 방법으로는 문제를 해결할 수가 없었다.

반대로 문제를 해결해보거나 하는 여러 관점을 생각해보아야겠다.

아직 문제를 보는 수준이 많이 부족하다고 느낀다.