[BeakJoon 17070] 파이프 옮기기1

안녕하세요. 이번 포스팅에서는 백준 17070 파이프 옮기기1을 풀어보도록 하겠습니다.

 

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

17070번: 파이프 옮기기 1

 

이 문제는 분류상 DP긴 한데,

 

저는 이 문제의 경우 역행하는 경우의 수도 없고, 고려해야할 경우의 수도 최대 16x16x7이기 때문에 BFS로 풀었습니다.

 

<소스 코드(BFS)>

#include<bits/stdc++.h>
using namespace std; 

int n, res, board[17][17];
const int dir[3][2] = {{0,1},{1,1},{1,0}};
typedef struct pipe{
	int y, x, dir;
}PIPE;
bool check(int y, int x, int d) {
	int ny = y+dir[d][0], nx = x+dir[d][1];
	if(ny > n || nx > n || ny < 1 || nx < 1) return false;
	if(board[ny][nx]) return false; 
	if(d == 1 && (board[y][x+1] || board[y+1][x])) return false;
	return true;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) cin >> board[i][j];
	}
	
	PIPE start = {1, 2, 0};
	queue<PIPE> q;
	
	q.push(start);
	while(!q.empty()) {
		PIPE cur = q.front(); q.pop();
		int y=cur.y, x=cur.x, d=cur.dir;
		if(y==n && x==n) {
			res++; continue;
		}
		if(d==0) {
			for(int i : {0, 1}) {
				int ny = y+dir[i][0], nx = x+dir[i][1];
				if(check(y,x,i)) q.push({ny,nx,i});
			}
		} else if(d==1) {
			for(int i : {0, 1, 2}) {
				int ny = y+dir[i][0], nx = x+dir[i][1];
				if(check(y,x,i)) q.push({ny,nx,i});
			}
		} else {
			for(int i : {1, 2}) {
				int ny = y+dir[i][0], nx = x+dir[i][1];
				if(check(y,x,i)) q.push({ny,nx,i});
			}
		}
	}
	
	cout << res << endl;
	return 0; 
}

 

DP의 풀이의 경우 배열을 3차원으로 선언하신 뒤, 각 dir의 정보에 맞추어 더해나가면서 풀어주시면 됩니다.

 

<소스 코드(DP)>

#include <bits/stdc++.h>
using namespace std;

int n, board[18][18];
int dp[18][18][3];
bool check(int y, int x, int dir) {
	if(dir == 0 || dir == 1) {
		return board[y][x] == 0;
	} else if(dir == 2) {
		return (board[y][x] == 0 && board[y-1][x] == 0 && board[y][x-1] == 0);	
	} 
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) cin >> board[i][j];
	}
	
	dp[0][1][0] = 1;
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(check(i, j+1, 0)) dp[i][j+1][0] += dp[i][j][0];
			if(check(i+1, j+1, 2)) dp[i+1][j+1][2] += dp[i][j][0];
			
			if(check(i+1, j, 1)) dp[i+1][j][1] += dp[i][j][1];
			if(check(i+1, j+1, 2)) dp[i+1][j+1][2] += dp[i][j][1];
			
			if(check(i, j+1, 0)) dp[i][j+1][0] += dp[i][j][2];
			if(check(i+1, j, 1)) dp[i+1][j][1] += dp[i][j][2];
			if(check(i+1, j+1, 2)) dp[i+1][j+1][2] += dp[i][j][2];
			
		}
	}
	
	cout << dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2];
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.