[ 백준 17070 ] 파이프 옮기기1 (C++)

백준의 파이프 옮기기1(17070) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 파이프를 (0, 0)에서 (N-1, N-1)까지 옮기는 경우의 수가 총 몇가지 있는지 구하는 문제이다. 파이프는 오른쪽,

   아래쪽, 오른쪽 아래 대각선 이렇게 총 3방향으로만 움직일 수 있으며 이 때 경우의 수를 구해야 한다.

   N값이 16으로 그리 크지 않은 값이기 때문에 넓이우선탐색 기법인 BFS로 완전탐색을 진행해보았다.

2) 파이프는 처음에 (1, 1)과 (1, 2)를 차지하고 있는 가로방향으로 존재한다고 했다. 문제에서는 이렇게 주어졌지만 본인은 애초에

   맵을 (0, 0) ~ (N - 1, N - 1)로 잡았기 때문에 (0, 0)과 (0, 1)에 존재한다고 구현해주었다.

   또한 본인은, 파이프를 2칸이 아닌 가장 앞쪽에 있는 한칸만으로 계산을 해 주었다. 즉, 파이프의 초기상태를 (0, 1)에 동쪽을

   향하는 방향으로 설정해 주었다.

   본인은 BFS를 구현할 때 사용되는 Queue에서 3가지 변수를 관리해주었다. x좌표, y좌표, 현재 진행방향

  

3) BFS 에서의 조건은 이렇다. 현재 진행방향이 동쪽 혹은 남쪽이라면 그 방향 그대로 진행하는 것과,

   대각선으로 진행하는 것 이 2가지에 대해서 판단해주었다. 대각선으로 나아갈 때는, (현재 x좌표 + 1 , 현재 y좌표) 와

   (현재 x좌표, 현재 y좌표 + 1)의 좌표값들이 0이어야만 진행할 수 있다는 것도 주의해주자.

   대각선으로 진행할 때에는, 동쪽으로 방향을 바꾸는 것, 남쪽으로 방향을 바꾸는 것, 대각선 방향 그대로 진행하는 것 이렇게

   총 3가지에 대해서 구현해 주었다.

   Queue에서 관리하고 있는 현재 x좌표와 y좌표가 N - 1이라면, 해당 Queue에서는 더이상 탐색하지 않고 그대로 넘어가버리도록

   구현해 주었다.

   DFS로도 구현을 해 보았는데, DFS로도 구현이 가능하다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 16
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
queue<pair<pair<int, int>, int > > Q;
 
int dx[] = { 0, 1, 1 };
int dy[] = { 1, 0, 1 };
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void BFS()
{
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Dir = Q.front().second;
        Q.pop();
 
        if (x == N - 1 && y == N - 1)
        {
            Answer++;
            continue;
        }
 
        if (Dir == 0)    // 동쪽으로 향할때
        {    
            int nx = x + dx[Dir];
            int ny = y + dy[Dir];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == 0)
                {
                    Q.push(make_pair(make_pair(nx, ny), Dir));
                }
            }
 
            nx = x + dx[2];
            ny = y + dy[2];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == 0 && MAP[x + 1][y] == 0 && MAP[x][y + 1] == 0)
                {
                    Q.push(make_pair(make_pair(nx, ny), 2));
                }
            }
        }
        else if (Dir == 1)
        {
            int nx = x + dx[Dir];
            int ny = y + dy[Dir];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == 0)
                {
                    Q.push(make_pair(make_pair(nx, ny), Dir));
                }
            }
 
            nx = x + dx[2];
            ny = y + dy[2];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == 0 && MAP[x + 1][y] == 0 && MAP[x][y + 1] == 0)
                {
                    Q.push(make_pair(make_pair(nx, ny), 2));
                }
            }
        }
        else if (Dir == 2)
        {
            int nx = x + dx[Dir];
            int ny = y + dy[Dir];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == 0 && MAP[x + 1][y] == 0 && MAP[x][y + 1] == 0)
                {
                    Q.push(make_pair(make_pair(nx, ny), Dir));
                }
            }
 
            for (int i = 0; i < 2; i++)
            {
                nx = x + dx[i];
                ny = y + dy[i];
 
                if (nx >= 0 && ny >= 0 && nx < N  && ny < N)
                {
                    if (MAP[nx][ny] == 0)
                    {
                        Q.push(make_pair(make_pair(nx, ny), i));
                    }
                }
            }
        }
    }
}
 
void Solution()
{
    Q.push(make_pair(make_pair(0, 1), 0));
    BFS();
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}