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

문제 링크

---

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

접근 방법

---

어렵지 않게 풀 수 있는 문제였으나, DP테이블을 설계 할 때 고려해야 할 점이 하나 있습니다.

위의 그림은 모두 같은 위치에 있지만, 해당 위치에서 파이프의 방향에 따라 앞으로 진행될 경우가 모두 다르다는 것을 생각 할 수 있다. 즉 DP테이블을 dp[가로][세로][3]으로 생각하여 문제를 해결하면 된다.  

 

소스 코드

---

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int n;
int map[16][16];
int dp[16][16][3];

bool isPossible(int x, int y, int dir) {
	if (x >= n || y >= n)
		return false;
	if (dir == 0 || dir == 1) 
		if (map[x][y] == 1) 
			return false;
	if (dir == 2)
		if (map[x][y] == 1 || map[x - 1][y] == 1 || map[x][y - 1] == 1)
			return false;
	return true;
}

int solve(int x, int y, int dir) { //dir 0 오른, 1 아래, 2 대각

	if (!isPossible(x, y, dir)) 
		return 0;
	
	int &ref = dp[x][y][dir];

	if (ref != -1) 
		return ref;
	ref = 0;

	if (x == n - 1 && y == n - 1) 
		return ref = 1;

	if (dir == 0) { // 오른쪽일때
			ref += solve(x, y + 1, 0); //오른쪽 그대로
			ref += solve(x + 1, y + 1, 2); //대각으로
	}
	else if (dir == 1) { // 아래일때
			ref += solve(x + 1, y, 1); //아래 그대로
			ref += solve(x + 1, y + 1, 2); //대각으로
	}
	else { //대각 일 때
			ref += solve(x, y + 1, 0); //오른쪽로 가거나
			ref += solve(x + 1, y, 1); //아래로 가거나
			ref += solve(x + 1, y + 1, 2); //대각으로 가거나
	}
	return ref;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << solve(0,1,0);
}

개발 환경 : VS2017

질문, 지적 환영합니다!