[백준] 골드5 : (17070) 파이프 옮기기 1

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

 

문제가 그래프로 되어있어서 처음에 생각한 방식인 BFS를 통해 풀었다.

풀고 보니, 정석적인 문제 풀이는 DP를 통해 푸는 것이더라.

 

파이프는 →, ↘, ↓ 방향으로만 갈 수 있다.

이는 각 방향 좌표쌍을 순서대로 저장하여 사용한다.

 

문제 풀이는 단순하게 현재 끝 파이프의 위치에서 →, ↘, ↓ 방향의 좌표를 queue에 넣는 BFS 방식으로 풀었다.

 

풀이의 핵심은 파이프가 자신의 방향에서 45º씩 밖에 회전할 수 없다는 점이다.

즉, 가로의 경우 가로, 대각선으로만 갈 수 있다. (대각선은 가로, 대각, 세로 다 됨)

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

// 방향 좌표쌍
int dy[]{ 0, 1, 1 };
int dx[]{ 1, 1, 0 };
int N, Answer;

void Func(const int& y, const int& x, const int& Type, const int& Start, const int& End, queue<tuple<int, int, int>>& q, const vector<vector<int>>& House)
{
	for (int i = Start; i < End; ++i)
	{
		int ny = y + dy[i], nx = x + dx[i];
		if (ny >= N || nx >= N || House[ny][nx] == 1) continue;

		// 대각 파이프의 경우, 연결한 지점의 '좌', '상' 지점이 비어있는지 추가 확인
		if (i == 1) if (ny - 1 >= N || nx - 1 >= N || House[ny - 1][nx] != 0 || House[ny][nx - 1] != 0) continue;

		// 연결한 지점이 도착 지점이면 끝
		if (ny == N - 1 && nx == N - 1) Answer++;
		// 수직 파이프의 경우엔 검사 시작 범위가 1이기 때문에, 수직 유형이 나오면 1을 더해서 수직으로 넘겨줘야 함
		else if (Type == 2) q.push({ ny, nx, abs(Start - i) + 1 });
		else q.push({ ny, nx, abs(Start - i) });
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	vector<vector<int>> House(N, vector<int>(N, 0));

	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x)
			cin >> House[y][x];

	// [0] = Y, [1] = X, [2] = 방향 (가로(0), 대각(1), 세로(2))
	queue<tuple<int, int, int>> q;
	q.push({ 0, 1, 0 }); // 시작은 { 0, 0 } ~ { 0, 1 } 가로 방향으로 시작

	while (!q.empty())
	{
		int y = get<0>(q.front()), x = get<1>(q.front()), Type = get<2>(q.front());
		q.pop();

		switch (Type)
		{
		case 0: Func(y, x, Type, 0, 2, q, House); break; // 가로 (가로, 대각 연결 가능)
		case 1: Func(y, x, Type, 0, 3, q, House); break; // 대각 (가로, 대각, 세로 연결 가능)
		case 2: Func(y, x, Type, 1, 3, q, House); break; // 세로 (대각, 세로 연결 가능)
		default: break;
		}
	}
	cout << Answer << "\n";
}