[백준 17070] 파이프 옮기기 1

안녕하세요 !!! 우디 입니다 ~
이번에는 BFS 로 푸는 파이프 옮기기에 대해서 설명해 드릴께요.

문제 설명

이 문제는 모든 경우를 다 살펴봐야 합니다.

우선 파이프가

• 가로 방향일 때 -> 가로 or 대각선 으로 이동 가능
• 세로 방향일 때 -> 세로 or 대각선 으로 이동 가능
• 대각선 방향일 때 -> 가로 or 세로 or 대각선 으로 이동 가능
  
  위 처럼 각 방향마다 이동 반경이 정해져 있고, 시작은 무조건 가로 방향부터 시작하니 아래 트리처럼 나타낼 수 있습니다.

이렇게 트리 형식으로 가로로 계속 경우의 수를 늘리다 보면 최종 (N,N)에 도착할 때 마다 갯수를 세어주면 되므로 이 문제는 그래프 탐색 기법의 큐를 기반으로 한 BFS 로 풀면 됩니다.

구현

저는 큐를 2개 사용해 주었습니다.
하나는 파이프의 움직일(?끝쪽?) 좌표 쌍을 담는 pair 큐 하나와 그 좌표가 어느 방향에 놓여져 있는지 알려주는 숫자를 담는 방향 큐를 만들어 주었습니다.( 1 : 가로 2 : 세로 3 : 대각선 )

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

int arr[20][20];

int main()
{
    int n; //N
    int answer = 0;// 정답
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];

    queue<pair<int, int>> q1;
    queue <int> q2;//1: 가로 2: 세로 3: 대각선

    q1.push(make_pair(0, 1));
    q2.push(1);//처음 시작 파이프 좌표 (0,1)과 가로방향 1 큐에 넣음.

    while (!q1.empty())//큐가 다 비어지면 종료
    {
        int x = q1.front().first;
        int y = q1.front().second;
        int dir = q2.front();

        if (x + 1 == n && y + 1 == n) answer++;//(N,N)에 도달하면 정답 +1 해줌.

        q1.pop();
        q2.pop();

        if (dir == 1)//가로 방향
        {
            if (arr[x][y + 1] != 1 && y + 1 != n)
            {
                q1.push(make_pair(x, y + 1));
                q2.push(1);
            }//옮길려는 위치가 벽이거나 배열 사이즈 넘어가지 않게 조건문 검 (아래 모두가 그렇숨돠!)
            if (arr[x + 1][y + 1] != 1 && arr[x][y + 1] != 1 && arr[x + 1][y] != 1
                && x + 1 != n && y + 1 != n)
            {
                q1.push(make_pair(x + 1, y + 1));
                q2.push(3);
            }
        }
        else if (dir == 2)//세로 방향
        {
            if (arr[x + 1][y] != 1 && x + 1 != n)
            {
                q1.push(make_pair(x + 1, y));
                q2.push(2);
            }
            if (arr[x + 1][y + 1] != 1 && arr[x][y + 1] != 1 && arr[x + 1][y] != 1 && x + 1 != n && y + 1 != n)
            {
                q1.push(make_pair(x + 1, y + 1));
                q2.push(3);
            }
        }
        else//대각선 방향
        {
            if (arr[x][y + 1] != 1 && y + 1 != n)
            {
                q1.push(make_pair(x, y + 1));
                q2.push(1);
            }
            if (arr[x + 1][y] != 1 && x + 1 != n)
            {
                q1.push(make_pair(x + 1, y));
                q2.push(2);
            }
            if (arr[x + 1][y + 1] != 1 && arr[x][y + 1] != 1 && arr[x + 1][y] != 1 && x + 1 != n && y + 1 != n)
            {
                q1.push(make_pair(x + 1, y + 1));
                q2.push(3);
            }
        }
    }//while문 끝

    cout << answer << endl; //정답 출력
}

어려운 점 및 개선점

마크다운이 HTML 소속인 거 첨 알았구 ,,,
HTML 제대로 안써봐서 단순하듯 더 어렵구 ,,,
그치만 꾸미는 데 집착있는 나눈 계속 붙잡구 있구 ,,,
언젠간 자유자재로 꾸밀 수 있는 날이 올거라 믿는닷 !