17070 파이프 옮기기 1

17070 파이프 옮기기 1 (c++)

문제

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

접근 방식

BFS

1. N x N 인 정사각형 격자판
2. 파이프는 2칸을 차지
3. 이동할 수 있는 경로는 3가지
   1. 오른쪽 (가로)
   2. 아래 (세로)
   3. 우하향 (대각선)
4. 각각 현재 상태에 따라 이동할 수 있는 경우가 제한된다.
   1. 현재 상태 가로 : 가로, 대각선
   2. 현재 상태 세로 : 세로, 대각선
   3. 현재 상태 대각선 : 가로, 세로, 대각선
5. 격자는 0 (빈칸) 과 1 (벽) 으로 이루어져 있다.
6. 1,2에서 시작해서 N,N까지 갈 수 있는 경우의 수를 구하시오.

BFS로 탐색을 하되, 현재 파이프의 상태가 탐색 방법을 정하는 key가 된다.
파이프는 2칸을 차지한다고 하지만, 실상 파이프의 우측 부분만을 고려하면 된다. (그래서 시작점은 1,2)
N, N에 도착하게 되면, 경우의 수가 한가지 늘어난 것이므로 answer++ 해준다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, answer = 0;
vector<vector<int>> board;


// 0 : 가로
// 1 : 세로
// 2 : 대각선
void BFS()
{
    queue <pair<pair<int, int>, int>> q;
    q.push({ {0, 1}, 0 });

    while (!q.empty())
    {
        pair<pair<int, int>, int> now = q.front(); q.pop();

        if (now.first.first == N - 1 && now.first.second == N - 1)
        {
            answer++;
            continue;
        }

        switch (now.second)
        {
        case 0:
            // 가로
            if (now.first.second + 1 < N && board[now.first.first][now.first.second + 1] == 0)
            {
                q.push({ {now.first.first, now.first.second + 1}, 0 });
            }
            // 대각선
            if (now.first.first + 1 < N && now.first.second + 1 < N &&
                board[now.first.first + 1][now.first.second + 1] == 0 &&
                board[now.first.first + 1][now.first.second] == 0 &&
                board[now.first.first][now.first.second + 1] == 0)
            {
                q.push({ {now.first.first + 1, now.first.second + 1}, 2 });
            }
            break;
        case 1:
            // 대각선
            if (now.first.first + 1 < N && now.first.second + 1 < N &&
                board[now.first.first + 1][now.first.second + 1] == 0 &&
                board[now.first.first + 1][now.first.second] == 0 &&
                board[now.first.first][now.first.second + 1] == 0)
            {
                q.push({ {now.first.first + 1, now.first.second + 1}, 2 });
            }
            // 세로
            if (now.first.first + 1 < N && board[now.first.first + 1][now.first.second] == 0)
            {
                q.push({ {now.first.first + 1, now.first.second}, 1 });
            }
            break;
        case 2:
            // 가로
            if (now.first.second + 1 < N && board[now.first.first][now.first.second + 1] == 0)
            {
                q.push({ {now.first.first, now.first.second + 1}, 0 });
            }
            // 대각선
            if (now.first.first + 1 < N && now.first.second + 1 < N &&
                board[now.first.first + 1][now.first.second + 1] == 0 &&
                board[now.first.first + 1][now.first.second] == 0 &&
                board[now.first.first][now.first.second + 1] == 0)
            {
                q.push({ {now.first.first + 1, now.first.second + 1}, 2 });
            }
            // 세로
            if (now.first.first + 1 < N && board[now.first.first + 1][now.first.second] == 0)
            {
                q.push({ {now.first.first + 1, now.first.second}, 1 });
            }
            break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    board = vector<vector<int>>(N, vector<int>(N + 1));

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> board[i][j];
        }
    }

    BFS();

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 한번에 해결했다. 문제를 정확히 이해하고, 풀이방법을 생각해냈다.
2. 하지만 메모리와 시간 효율이 형편없었다. 다른 사람들의 풀이를 보고 개선점을 찾아야 한다.
3. 격자칸에서의 이동을 보고 BFS인 것을 찾아냈다.
4. 현재 파이프의 상태가 중요하기때문에 정보값을 넣어서 전달했다.
5. 파이프의 상태에 따라 이동할 수 있는 경우가 달리지기 때문에 switch 문을 활용