백준 1343 - 폴리오미노 (자바 - 그리디)

오랜만에 작성하는 블로그 글 겸 백준 문제풀이글

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

1343번: 폴리오미노

 

* 문제 요약

다음과 같은 폴리오미노를 무한개만큼 가지고 있다 - AAAA, BB

'.' 와 'X' 로 이루어진 보드판이 주어졌을 때, 겹침없이 'X' 를 모두 폴리오미노로 덮으려고 한다.

이때 '.' 는 폴리오미노로 덮으면 안된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오

 

* 입력

- 보드판이 주어진다, 크기는 최대 50이다.

* 출력

- 사전순으로 가장 앞서는 답을 출력한다.

- 만약 덮을 수 없다면 -1을 출력한다.

 

* 예시

 

* 해결 과정

1. 문자열을 처음부터 끝까지 탐색하되 조건은 '.' 을 탐색했을 때와 'X' 를 탐색했을 때로 나눈다.

2. 사전순으로 가장 앞서는 답을 출력해야 하기에 AAAA 로 문자열을 덮을 수 있는지부터 먼저 확인하고

그 다음에 BB 로 덮을 수 있는지 확인한다.

 

*  '.' 을 탐색했을 경우

- 현재까지 몇개의 X 를 탐색했는지 확인한다.

- 만약 '.' 을 만나기전에 'X' 를 4개 연달아 탐색한 상태라면 정답 문자열에 AAAA 를 추가하고 그 뒤에 '.' 를 붙여준 뒤

'X' 탐색 횟수를 0 으로 초기화 해준다.

- 만약 '.' 을 만나기 전에 'X' 를 2개 연달아 탐색한 상태라면 정답 문자열에 BB 를 추가하고 그 뒤에 '.' 를 붙여준 뒤,

'X' 탐색 횟수를 0 으로 초기화 해준다.

- 만약 '.' 를 만나기 전에 'X' 가 탐색되지 않은 상태인 경우, 즉 X 탐색 횟수가 0 인 경우 정답 문자열에 '.' 만 붙여준다.

- 만약 '.' 를 만나기 전에 'X' 탐색 횟수가 4,2,0 중 하나가 아니라면 어떤 폴리오미노 로도 문자열을 겹칠수 없다는 뜻이므로 -1 을 출력한다. 

 

* 'X' 를 탐색했을 경우

- 'X' 탐색 횟수를 1 추가한다.

- 만약 현재 'X' 탐색 횟수가 4 가 되었을 경우 정답 문자열에 AAAA 를 추가해주고 'X' 탐색 횟수를 0 으로 초기화한다.

- 만약 현재 'X' 탐색 횟수가 2 인 동시에(And) 현재 탐색 위치가 문자열의 마지막이라면 정답 문자열에 BB 를 추가해준다.

(문자열의 마지막인지 여부를 조건에 추가해준 이유 : 일단 사전순으로 가장 앞서는 문자열을 출력해야 하기에 되도록이면 문자열의 앞 부분을 AAAA 로 채워줘야 한다. 즉, AAAA 2개 사이에 BB 가 덮여지는 상황을 최대한 피해야 한다.)

(그렇기에 문자열의 앞 부분은 최대한 AAAA 로 채워나가고 BB 는 '.' 을 만났거나 문자열의 거의 끝 부분인 상황에서만 고려해주는 것이 좋다.)

- 만약 현재 'X' 의 탐색 횟수가 4, 또는 2가 아닌 상황에서 문자열의 마지막에 도달했을 경우 입력받은 문자열을 AAAA, BB 로 완벽하게 채울 수 없다는 뜻이므로 -1 을 출력해준다.

 

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String polioStr = br.readLine();
        String polio = "";
        boolean polioBool = true;

        int count = 0;
        for(int i = 0; i < polioStr.length(); i++){

            if(polioStr.charAt(i) == '.'){
                if(count == 4){
                    count = 0;
                    polio += "AAAA.";
                }
                else if(count == 2){
                    count = 0;
                    polio += "BB.";
                }
                else if(count == 0){
                    polio += ".";
                }
                else{
                    // -1 출력
                    polioBool = false;
                    break;
                }
            }
            else if(polioStr.charAt(i) == 'X'){
                count++;
                if(count == 4){
                    polio += "AAAA";
                    count = 0;
                }
                else if(count == 2 && i == polioStr.length()-1){
                    polio += "BB";
                }
                else if(i == polioStr.length()-1){
                    polioBool = false;
                }
            }
        }

        if(!polioBool){
            bw.write("-1");
        }
        else{
            bw.write(polio);
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

매 반복마다 여러 가지 조건들 중에서 X 의 탐색 횟수. 즉, 현재 상황에 따라 최적의 조건을 찾아 수행하게 되므로 그리디 알고리즘 문제라고 할 수 있다.