BOJ_17069 [ 파이프 옮기기2 ]

문제

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

17069번: 파이프 옮기기 2

 

문제 해결 방법

단순히 bfs 로 문제를 해결하면 메모리초과가 발생한다.

이 문제를 해결하기 위해서는 다이나믹 프로그래밍으로 접근해야 된다.

2중 포문을 돌면서 이동 가능한 방향을 dp [방향][y좌표][x좌표] 에 값을 계속 더해주면 된다.

dp 값이 0이라면 해당 좌표로는 이동된 경우가 없으므로 0이 아닌 경우에만 더해주면 쉽게 문제를 해결할 수 있다.

 

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 33
int N;
int board[MAX][MAX];
long long dp[3][MAX][MAX];	//0 가로 //1 세로 // 2 대각선


int main() {
	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][0][1] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//가로로 이동하는 경우 현재 좌표에서 가로 대각선이 0이 아니여야된다.
			if (board[i][j + 1] == 0&&(dp[0][i][j]!=0||dp[2][i][j]!=0)) {
				dp[0][i][j + 1] += (dp[0][i][j] + dp[2][i][j]);
			}
			//세로로 이동하는 경우
			if (board[i + 1][j] == 0&&(dp[1][i][j]!=0||dp[2][i][j]!=0)) {
				dp[1][i+1][j] += (dp[1][i][j] + dp[2][i][j]);
			}
			//대각선으로 이동하는 경우
			if ((board[i + 1][j + 1] == 0&&board[i+1][j]==0&&board[i][j+1]==0 )&& (dp[0][i][j] != 0 ||dp[1][i][j]!=0|| dp[2][i][j] != 0)) {
				dp[2][i + 1][j+1] += (dp[0][i][j]+dp[1][i][j] + dp[2][i][j]);
			}
		}
	}

	cout << dp[0][N - 1][N - 1] + dp[1][N - 1][N - 1] + dp[2][N - 1][N - 1] << '\n';
	
	return 0;
}

 

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/Dynamic%20programming/boj_17069.cpp

jokerKwu/BOJ_Algorithm