14601번: 샤워실 바닥 깔기 (플래티넘 5)

14601번: 샤워실 바닥 깔기 (Large) (acmicpc.net)

14601번: 샤워실 바닥 깔기 (Large)

 

1. 문제 설명

(1) 오늘은 민규가 훈련소에 입소하는 날이다. 모든 행사를 마치고 생활관으로 돌아와서 쉬려는데 갑자기 교관이 들어오더니 민규의 이름을 부르는 것이 아닌가. 당황한 채로 따라갔더니 이번엔 김준서를 아느냐고 물어보았다. 그 녀석이 샤워실 바닥을 깔았는데, 배수구 위치까지 막아버렸다면서 같은 학교 출신인 민규가 다시 깔라는 것이었다.

 

(2) 어떻게 타일을 깔지 고민하던 민규는 샤워실의 구조가 정사각형이면서 한 변의 길이가 2의 제곱수라는 사실을 알아냈다. 준서는 여기까지만 고려해서 2x2 크기의 타일로 바닥을 전부 채운 것 같은데, 문제는 이렇게 하면 배수구가 있어야 할 위치를 비울 수가 없다는 것이다. 이런저런 방법을 생각하다가 4칸을 차지하는 정사각형 타일 대신 3칸을 차지하는 ㄱ자 모양의 타일을 사용하면 될 것 같다는 느낌을 받았다.

 

(3) 그런데 ㄱ자 타일을 어떻게 채워야 할까? 생각하다 지친 민규는 여러분에게 이 방법을 찾아달라고 부탁했다. 첫날부터 생활관에서 밤을 새우는 일이 없도록 여러분이 도와주자.

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다.

*이때 바닥의 크기는 2K 가 됨에 유의하라.

(2) 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K)가 공백으로 분리돼서 주어진다.

*이때 가장 왼쪽 아래가 (1, 1), 가장 오른쪽 위가 (2K, 2K)이다.

 

출력 조건

(1) 각 타일마다 고유한 번호를 매긴 타일의 배치도를 출력한다.

(2) 각 타일의 번호에는 19000 이하의 자연수만을 사용해야 한다.

(3) 배수구가 있는 위치는 -1로 표시한다. 가능한 답 중 하나만 출력하면 된다.

(4) 만약 알맞게 타일을 배치하는 방법이 존재하지 않는다면 -1을 출력한다.

 

 

입출력 예제

 

 

 

 

3. 제약 조건

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 힌트

 

 

 

 

7. 코드

: 이 문제를 풀면서 예전에 풀었던 완전 탐색 문제 "게임판 덮기(BOARDCOVER)"를 떠올리면서 문제를 해결했다.

 

게임판 덮기 (난이도: 하) (tistory.com)

게임판 덮기 (난이도: 하)

 

 

- 이 둘의 문제 공통점은 결국 재귀 호출로 다 한 번씩 타일을 놓을 수 있는 지 없는 지 여부를 확인하는 데 있다.

 

- 단, 게임판 덮기는 그냥 모든 경우의 수를 구하는 데 그치지만 이 타일 문제는 구멍의 위치를 확인하면서 놓는 순서를

정해야 하는 데 차이가 발생한다.

 

 

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

public class Main {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int[][] A;
    private static int num, N, x, y;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        N = Integer.parseInt(sc.readLine());
        N = (int)Math.pow(2, N);
        A = new int[N+1][N+1];

        st = new StringTokenizer(sc.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());

        A[x][y] = -1;

        solve(1, 1, N);
        print();
    }

    private static void solve(int x, int y, int size) {

        // 초기 타일은 1번부터 시작
        // 그 후는 ++ 하여 타일 번호를 지정
        num++;

        // 1,2,3,4 사분면을 나누기 위해 /2를 수행
        int ns=size/2;

        // 각각 1, 3, 2, 4 사분면에 대해 타일을 둘 것인지
        // 확인하는 check() 메서드를 수행하는 과정
        if(check(x,y,ns)) A[x+ns-1][y+ns-1]=num;
        if(check(x+ns,y,ns)) A[x+ns][y+ns-1]=num;
        if(check(x,y+ns,ns)) A[x+ns-1][y+ns]=num;
        if(check(x+ns,y+ns,ns)) A[x+ns][y+ns]=num;

        // 기저 사례(1): 타일(size)를 더 나눌 수 없을 경우
        if(size==2) return;

        // 1,2,3,4 사분면으로 쪼개어
        // 재귀호출을 수행한다.
        solve(x,y,ns);
        solve(x+ns,y,ns);
        solve(x,y+ns,ns);
        solve(x+ns,y+ns,ns);
    }

    // 해당 위치에 타일을 놓을 수 있는지 확인하는 메서드
    public static boolean check(int x,int y,int size){
        for(int i=x; i<x+size; i++){
            for(int j=y; j<y+size; j++){
                if(A[i][j] != 0) return false;
            }
        }
        return true;
    }

    // 이중 배열을 출력하는 메서드
    public static void print(){
        for(int i=N;i>=1;i--){
            for(int j=1;j<=N;j++){
                System.out.printf(A[j][i]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }
}