백준 17070 파이프 옮기기 1

BOJ 17070

목표 : 파이프를 배치해 N*N칸으로 이동하자. 파이프는 가로, 세로, 대각선 3종류가 있다.

조건 : 3 <= N <= 16

해결방안

BFS를 통해 문제를 해결했다. 가로 파이프에서는 가로, 대각선, 세로 파이프에서는 세로, 대각선, 대각선 파이프에서는 모든 파이프를 설치할 수 있다. 추가로 설치할 곳에 벽이 있거나 배열을 나가지 않는지 체크하자.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,M, input[16][16];
queue<pair<pair<int,int>,int>> Q;

bool isin(int x, int y){
	return x >= 0 && y >= 0 && x < N && y < N;
}

int main(){
    scanf("%d",&N);
    for (int i = 0; i < N; i++){
    	for (int j = 0; j < N; j++){
    		scanf("%d",&input[i][j]);
		}
	}
    int ans = 0;
	Q.push({{0,1},0});
	while(!Q.empty()){
		int cx = Q.front().first.first;
		int cy = Q.front().first.second;
		int dir = Q.front().second;
		Q.pop();
        if (cx == N-1 && cy == N-1){
            ans++;
            continue;
        }
		if (!dir){
			if (isin(cx,cy+1) && !input[cx][cy+1]){
				Q.push({{cx,cy+1},0});
			}
			if (isin(cx+1,cy+1) && !input[cx][cy+1] && !input[cx+1][cy] && !input[cx+1][cy+1]){
				Q.push({{cx+1,cy+1},2});
			}
		}
		else if (dir == 1){
			if (isin(cx+1,cy) && !input[cx+1][cy]){
				Q.push({{cx+1,cy},1});
			}
			if (isin(cx+1,cy+1) && !input[cx][cy+1] && !input[cx+1][cy] && !input[cx+1][cy+1]){
				Q.push({{cx+1,cy+1},2});
			}
		}
		else{
			if (isin(cx,cy+1) && !input[cx][cy+1]){
				Q.push({{cx,cy+1},0});
			}
			if (isin(cx+1,cy) && !input[cx+1][cy]){
				Q.push({{cx+1,cy},1});
			}
			if (isin(cx+1,cy+1) && !input[cx][cy+1] && !input[cx+1][cy] && !input[cx+1][cy+1]){
				Q.push({{cx+1,cy+1},2});
			}
		}
	}
	
	printf("%d\n",ans);
    
    return 0;
}