백준 / 17070 파이프 옮기기1 C++

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

처음에 dp로 풀려다가 테스트케이스들이 주어진 것보다 훨씬 큰 값을 가지길래 뭔가 싶었는데 조건 만족할 때마다 이전 결과를 더 해주다보니 그런 것이었습니다. (문제만 읽으면 이렇게 하는 게 맞는 거 같은데 테스트 케이스에 있는 걸 손으로 그려보니 그냥 순수하게 끝 점에 도달하는 횟수를 의미하는 것이었다.)

 

그래서 그냥 bfs로 바꿔서 주어진 조건 만족할 때만 큐에 들어가도록 하여 풀었습니다.

 

코드는 다음과 같습니다.

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

using namespace std;

int n;
int map[17][17];
int result = 0;

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

void bfs()
{
	// 큐 : 방향, {파이프 끝의 좌표}, 방향 : 1,2,3 순으로 가로 세로 대각선
	queue<pair<int,pair<int, int>> >q;
	q.push({ 1,{ 1,2 } });

	while (!q.empty()) {
		int dir = q.front().first;
		int y = q.front().second.first;
		int x = q.front().second.second;

		if (y == n && x == n)
			result++;

		q.pop();

		if (dir == 1) {
			int ny, nx, ndir;

			// 가로로 이동
			ny = y;
			nx = x + 1;
			ndir = 1;

			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0) {
					q.push({ ndir, {ny, nx} });
				}
			}

			// 대각선 이동
			ny = y + 1;
			nx = x + 1;
			ndir = 3;


			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0 && map[ny][nx - 1] == 0 && map[ny - 1][nx] == 0){
					q.push({ ndir, {ny,nx} });
				}
			}
		}

		if (dir == 2) {
			int ny, nx, ndir;

			// 세로로 이동
			ny = y + 1;
			nx = x;
			ndir = 2;

			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0) {
					q.push({ ndir, {ny, nx} });
				}
			}

			// 대각선 이동
			ny = y + 1;
			nx = x + 1;
			ndir = 3;

			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0 && map[ny][nx - 1] == 0 && map[ny - 1][nx] == 0) {
					q.push({ ndir,{ny,nx} });
				}
			}
		}

		if (dir == 3) {
			int ny, nx, ndir;

			// 가로로 이동
			ny = y;
			nx = x + 1;
			ndir = 1;

			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0) {
					q.push({ ndir, {ny, nx} });
				}
			}

			// 세로로 이동
			ny = y + 1;
			nx = x;
			ndir = 2;

			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0) {
					q.push({ ndir, {ny, nx} });
				}
			}

			// 대각선 이동
			ny = y + 1;
			nx = x + 1;
			ndir = 3;

			if (ny > 0 && ny <= n && nx > 0 && nx <= n) {
				if (map[ny][nx] == 0 && map[ny][nx - 1] == 0 && map[ny - 1][nx] == 0) {
					q.push({ ndir,{ny,nx} });
				}
			}
		}
	}
}

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

	init();
	bfs();

	cout << result;
}