백준 1343번 폴리오미노 (JAVA)

https://www.acmicpc.net/problem/1343

1343번: 폴리오미노

 

저는 dfs를 통해 문제를 해결하였습니다.

각각의 문자를 보고 .이라면 바로 다음으로, 그것이 아니라면 해당 문자부터 4개중에 .이 있는지를 확인하고, 이 값을 토대로 dfs를 진행하였습니다. 2번째 문자까지 없다면 BB 4번째 문자까지 . 이 없다면 AAAA를 하여 문제를 해결하였습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_1343 {
    private static final String NOT_FOUND = "-1";
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String command = br.readLine();
        String result = cal(0,command,"");
        System.out.println(result);
    }

    private static String cal(int depth, String command, String now) {
        if(command.length() <= depth){
            return now;
        }
        if(command.charAt(depth)  == '.'){
            return cal(depth+1,command,now+".");
        }
        String result = NOT_FOUND;
        boolean[] isX = new boolean[4];
        Arrays.fill(isX,true);
        boolean flag = true;
        for(int i = 0 ; i < 4; i++){
            if(depth+i >= command.length()){
                break;
            }
            char ch = command.charAt(depth+i);
            if(ch == '.'){
                flag = false;
            }
            isX[i] = flag;
        }
        if(isX[1] && depth+1 < command.length()){
            String temp = cal(depth+2,command,now+"BB");
            if(result.equals(NOT_FOUND)){
                result = temp;
            }else if(result.compareTo(temp) > 0){
                result = temp;
            }

        }
        if(isX[3] && depth+3 < command.length()){
            String temp = cal(depth+4,command,now+"AAAA");
            if(result.equals(NOT_FOUND)){
                result = temp;
            }else if(result.compareTo(temp) > 0){
                result = temp;
            }
        }
        return result;
    }
}