[BOJ / DP] 17069 파이프 옮기기 2

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

17069번: 파이프 옮기기 2

 

17069 파이프 옮기기 2

알고리즘 : 우선순위큐, DP, 메모이제이션

3가지 파이프 상태에서 갈 수 있는 경우를 저장해서 3 * n * n  크기의 DP 배열을 만들어서 풀이합니다. 시간 초과를 피하기 위해 모든 경우의 수를 하는 것이 아닌 같은 경우인 곳을 합산하여 처리하고 작은 인덱스부터 처리하기 위해 우선순위 큐를 사용합니다. 

 

 

 

< CODE >

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define MAX 34

enum class DIR {
	RIGHT,
	DOWN,
	RIGHTDOWN,
};

struct Point {
	int y;
	int x;
};

struct forQ {
	Point p;
	DIR dir;
};

int n;
long long int weight[3][MAX][MAX];
int field[MAX][MAX];

int dx[] = { 1,0,1 };
int dy[] = { 0,1,1 };

priority_queue<forQ, vector<forQ>, greater<forQ>> q;

bool operator>(const forQ& a, const forQ& b) {
	if (a.p.y == b.p.y)
		return a.p.x > b.p.x;
	return a.p.y > b.p.y;
}

bool isSafe(Point p) {
	if (p.y <= n && p.x <= n)
		return true;
	return false;
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> field[i][j];
		}
	}

	q.push({ {1,2},DIR::RIGHT });
	weight[0][1][2] = 1;

	while (!q.empty()) {
		forQ cur = q.top(); q.pop();

		for (int i = 0; i < 3; i++) {
			if (((int)cur.dir + i) == 1)
				continue;
				
			int dY = cur.p.y + dy[i];
			int dX = cur.p.x + dx[i];
			bool possible = true;

			if (i == 2) {
				// 추가 검사
				possible = isSafe({ cur.p.y + 1,cur.p.x }) && isSafe({ cur.p.y,cur.p.x + 1}) && 
					(field[cur.p.y + 1][cur.p.x] == 0) && (field[cur.p.y][cur.p.x + 1] == 0);
			}

			possible = possible && isSafe({ dY,dX }) && (field[dY][dX] == 0);

			if (possible) {
				if (weight[i][dY][dX] == 0)
					q.push({ {dY,dX},(DIR)i });
				weight[i][dY][dX] += weight[(int)cur.dir][cur.p.y][cur.p.x];
			}
		}
	}

	cout << (weight[0][n][n] + weight[1][n][n] + weight[2][n][n]) << '\n';

	return 0;
}

시간 : 0ms

 

태그 : #BOJ 파이프 옮기기 2 #BOJ 파이프 옮기기 1 #17069 파이프 옮기기 2 #백준 파이프 옮기기