백준 17070번 파이프 옮기기 1 C++

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

파이프를 오른쪽으로 옮길 때에는 현재 위치에서 오른쪽 한 칸이 비어있어야 하고

아래로 옮길 때에는 아래에 한 칸이 비어있어야 한다. 

대각선으로 옮길 때에 주의해야할 점이 있는데, 대각선으로 간 칸과, 그 위칸과 왼쪽 칸 모두 비어있어야 한다는 것이다.

문제에도 비어있어야 할 칸이 색으로 칠해져있다.

 

나는 구조체를 만들어서 파이프의 위치와 현재 상태(오른쪽, 대각선, 아래 중 하나) 정보를 저장하고 그 구조체를 큐에 넣어서 bfs방식으로 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

struct info {
	info(int posRow, int posCol, int currstate) :posRow(posRow), posCol(posCol), currstate(currstate) {};
	int posRow; //행 정보
	int posCol; //열 정보
	int currstate; //현재 상태
};

enum currState {
	Right,
	Diagonal,
	Down
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<vector<int>> v(n + 1, vector<int>(n + 1, 0));
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
	queue<info> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> v[i][j];
		}
	}
    //처음 시작은 (1,2) 이고 파이프는 오른쪽을 보고 있는 상태이다.
	q.push(info(1, 2, currState::Right));
	dp[1][2] = 1;
	while (!q.empty()) {
		auto a = q.front();
		q.pop();
        //오른쪽 상태일 때는 오른쪽과 대각선을 검사한다.
		if (a.currstate == currState::Right) {
			if (a.posCol + 1 <= n && v[a.posRow][a.posCol + 1] == 0) {
				q.push(info(a.posRow, a.posCol + 1, currState::Right));
				dp[a.posRow][a.posCol + 1]++;
			}
            //대각선으로 간 칸과 그 칸의 위, 왼쪽 모두 검사
			if (a.posCol + 1 <= n && a.posRow + 1 <= n && v[a.posRow + 1][a.posCol + 1] == 0 && v[a.posRow][a.posCol + 1] == 0 && v[a.posRow + 1][a.posCol] == 0) {
				q.push(info(a.posRow + 1, a.posCol + 1, currState::Diagonal));
				dp[a.posRow + 1][a.posCol + 1]++;
			}
		}
        //대각선 상태일때는 오른쪽, 대각선, 아래 모두 검사한다.
		else if (a.currstate == currState::Diagonal) {
			if (a.posCol + 1 <= n && v[a.posRow][a.posCol + 1] == 0) {
				q.push(info(a.posRow, a.posCol + 1, currState::Right));
				dp[a.posRow][a.posCol + 1]++;
			}
			if (a.posCol + 1 <= n && a.posRow + 1 <= n && v[a.posRow + 1][a.posCol + 1] == 0 && v[a.posRow][a.posCol + 1] == 0 && v[a.posRow + 1][a.posCol] == 0) {
				q.push(info(a.posRow + 1, a.posCol + 1, currState::Diagonal));
				dp[a.posRow + 1][a.posCol + 1]++;
			}
			if (a.posRow + 1 <= n && v[a.posRow + 1][a.posCol] == 0) {
				q.push(info(a.posRow + 1, a.posCol, currState::Down));
				dp[a.posRow + 1][a.posCol]++;
			}
		}
        //아래 상태일 때는 대각선과 아래를 검사한다.
		else if (a.currstate == currState::Down) {
			if (a.posCol + 1 <= n && a.posRow + 1 <= n && v[a.posRow + 1][a.posCol + 1] == 0 && v[a.posRow][a.posCol + 1] == 0 && v[a.posRow + 1][a.posCol] == 0) {
				q.push(info(a.posRow + 1, a.posCol + 1, currState::Diagonal));
				dp[a.posRow + 1][a.posCol + 1]++;
			}
			if (a.posRow + 1 <= n && v[a.posRow + 1][a.posCol] == 0) {
				q.push(info(a.posRow + 1, a.posCol, currState::Down));
				dp[a.posRow + 1][a.posCol]++;
			}
		}
	}
	cout << dp[n][n];
};