[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1343번, 폴리오미노

문제 링크

1343번: 폴리오미노

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 폴리오미노는 "AAAA", "BB" 2개를 무한정 가지고 있습니다.

2. 'X'칸에만 폴리오미노로 덮을 수 있습니다.

3. 주어진 보드를 사전 순 가장 앞서는 폴리오미노로 덮은 결과를 출력합니다.

4. 폴리오미노로 모두 덮을 수 없다면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 연속되는 'X'에 따라 폴리오미노를 덮습니다.

 

3. 모두 덮을 수 있으면 덮은 결과를, 덮지 못하면 -1을 결과로 출력합니다.

 

 

폴리오미노 덮어쓰기.

 

폴리오미노를 덮었을 때 사전순으로 앞서려면 "AAAA"를 우선적으로 사용한 뒤 "BB"를 사용해야 합니다.

 

"AAAA"를 사용할 수 있는 경우.

 

연속된 'X'의 개수가 4배수일 때

 

"BB"를 사용할 수 있는 경우

 

연속된 'X'의 개수가 2일 때

 

예를 들어.

 

XXXXXX일 때

 

연속되는 'X'의 개수는 6개

 

6개  = 4 + 2 으로 표현이 가능합니다.

 

"AAAA" 개수 : 1개 = 6 ÷ 4 = 1개

 

"BB" 개수 : (6 % 4) ÷ 2 = 1개

 

"AAAABB"

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

보드

XX.XX

 

2. 연속되는 'X'에 따라 폴리오미노를 덮습니다.

 

'.'이 나올 때까지 'X'가 연속되는 개수 구하기!

 

XX.XX = 2개

 

연속된 'X'의 개수가 2개일 때에는 "BB" 사용!

 

'.'이 나올 때까지 'X'가 연속되는 개수 구하기!

 

XX.XX = 2개

 

연속된 'X'의 개수가 2개일 때에는 "BB" 사용!

 

3. 모두 덮을 수 있으면 덮은 결과를, 덮지 못하면 -1을 결과로 출력합니다.

 

모두 덮을 수 있기 때문에 덮은 결과 출력

 

"BB.BB"을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 보드의 각 글자를 탐색하여 'X'의 연속된 개수를 구합니다.
• 보드의 글자가 '.'일 때 지금까지 연속된 'X'의 개수를 check함수를 실행하여 폴리오미노 덮기를 진행합니다.
• 폴리오미노 덮기를 성공하면 덮인 보드를, 실패하면 -1를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• check함수는 연속된 'X'의 개수에 따라 폴리오미노 덮기를 진행합니다.

import java.io.*;

public class Main{
    static StringBuilder answer = new StringBuilder();
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        int count = 0;
        //보드의 각 글자 탐색
        for(int i=0;i<str.length();i++){
            char temp = str.charAt(i);
            if(temp == 'X')	//'X'일 때 연속된 개수 더하기!
                count++;
            else{	//'.'일 때 지금까지 연속된 'X'의 개수에 따라 덮어쓰기 진행!
                if(!check(count))		//폴리오미노로 덮어쓰기 불가능시 종료
                    break;
                answer.append(".");
                count = 0;	//연속된 개수 0으로 초기화
            }
        }
        //마지막 글자가 'X'로 끝날 때 남은 연속된 개수 폴리오미노로 덮기
        if(!answer.equals("-1") && str.charAt(str.length()-1) == 'X')
            check(count);
        bw.write(answer.toString());	//결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //폴리오미노 덮기 진행하는 함수
    static boolean check(int count){
        String A = "AAAA", B = "BB";	//폴리오미노 정보
        if(count % 4 == 0){	//4의 배수로 떨어질 때 "AAAA"만 사용!
            for(int j=0;j<count/4;j++)
                answer.append(A);
        }else if(count % 4 == 2){	//"AAAA"을 최대한 사용한 뒤 남은 칸 "BB"로 덮기
            for (int j = 0; j < count / 4; j++)
                answer.append(A);
            answer.append(B);
        }else if(count == 2)	//연속된 개수가 2개일 때 "BB" 한 번 사용
            answer.append(B);
        else {		//폴리오미노로 덮을 수 없을 때
            answer = new StringBuilder("-1");
            return false;
        }
        return true;
    }
}