[백준] 14600번 : 샤워실 바닥 깔기 (Small) (C++)

14600번 : 샤워실 바닥 깔기 (Small)

---

문제)

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

 

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

 

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

 

 

 

입력 :

첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2^K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2^K)가 공백으로 분리돼서 주어진다. 이때 가장 왼쪽 아래가 (1, 1), 가장 오른쪽 위가 (2^K, 2^K)이다.

 

 

 

출력 :

각 타일마다 고유한 번호를 매긴 타일의 배치도를 출력한다. 각 타일의 번호에는 19000 이하의 자연수만을 사용해야 한다. 배수구가 있는 위치는 -1로 표시한다. 가능한 답 중 하나만 출력하면 된다.

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

 

 

 

 

 

 

풀이)

 

// 14600. 샤워실 바닥 깔기 (Small)
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
bool complete = false;
vector<vector<int>> vec;
 
vector<vector<pair<int, int>>> block = 
{ 
    {{0, -1}, {0, 0}, {-1, 0}}, // ┘
    {{0, -1}, {0, 0}, {1, 0}},    // └
    {{-1, 0}, {0, 0}, {0, 1}},    // ┐
    {{1, 0}, {0, 0}, {0, 1}}    // ┌
};
 
void dfs(int cur, vector<vector<int>>& _vec, int cnt)
{
    if (complete) return;
 
    if (cnt == (n * n) - 1)
    {
        //for (int i = n - 1; i >= 0; i--)
        for (int i = 0; i < n; i++)
        {
            //for (int j = n - 1; j >= 0; j--)
            for (int j = 0; j < n; j++)
            {
                cout << _vec[i][j] << ' ';
            }
            cout << '\n';
        }
        complete = true;
        return;
    }
 
    // 모든 좌표에 대해
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 해당 좌표가 방문된적 없는 곳이라면
            if (_vec[i][j] == 0)
            {
                // 4가지 타일을 붙여본다.
                for (int k = 0; k < 4; k++)
                {
                    bool flag = 1;
                    // 각 타일을 확인.
                    for (int l = 0; l < 3; l++)
                    {
                        int nx = i + block[k][l].first;
                        int ny = j + block[k][l].second;
 
                        // 타일이 범위를 벗어나거나, 해당 위치에 이미 블록이 있다면
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n
                            || _vec[nx][ny] != 0)
                        {
                            flag = false;
                            break;
                        }
                    }
 
                    // 타일을 놓을 수 있다면 타일을 놓고 다음 배치로 넘어간다.
                    if (flag)
                    {
                        for (int l = 0; l < 3; l++)
                        {
                            int nx = i + block[k][l].first;
                            int ny = j + block[k][l].second;
 
                            _vec[nx][ny] = cur;
                            cnt++;
                        }
 
                        dfs(cur + 1, _vec, cnt);
 
                        for (int l = 0; l < 3; l++)
                        {
                            int nx = i + block[k][l].first;
                            int ny = j + block[k][l].second;
 
                            _vec[nx][ny] = 0;
                            cnt--;
                        }
 
                    }
                }
            }
        }
    }
}
 
 
int main()
{
    cin >> n;
    n *= 2;
    vec.resize(n, vector<int>(n, 0));
 
    int a, b;
    cin >> a >> b;
    vec[(n - 1) - (b - 1)][(a - 1)] = -1;
 
    dfs(1, vec, 0);
 
    if (!complete) cout << -1;
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/14600 

14600번: 샤워실 바닥 깔기 (Small)