[Baekjoon] 17070번 파이프 옮기기 1.cpp

[백준] 17070번 파이프 옮기기 1 문제 링크

· 최초 아이디어(BFS, 192ms)

특정 규칙에 맞게 최종 지점에 도달할 수 있는 경우의 수를 구하는 것. BFS나 DFS가 너무나도 떠오르는 문제이다. 따라서 BFS로 접근하였다. 규칙은 다음과 같다.

1. 파이프는 우, 우하, 하 방향으로만 이동할 수 있다.
2. 파이프는 45도만 회전할 수 있다. 즉, 우 방향 이후 하 방향으로 가거나 그 반대는 불가능하다.
3. 대각선으로 이동할 땐 우, 우하, 하 방향이 모두 벽이 아니어야 한다.

여기서 가장 우선이 돼야 하는 조건을 2번으로 두었다. 특정 좌표를 도달한 방향에 따라 다음 갈 수 있는 방향이 달라지기 때문에 어떤 방향으로 진입했는지를 먼저 점검할 필요가 있다. 이동이 가능하다면 다음 좌표와 진입 방향을 함께 저장하여 큐에 넣었다.

대각선 방향은 반드시 고려해야 하므로 현재 좌표의 진입 방향에 따라 우, 하 방향은 진입할지 말지를 결정하고 그에 따라 다음 좌표 설정 및 벽 체크를 해주었다.

해당 아이디어를 이용한 코드는 아래와 같다.

// BFS를 활용한 코드

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

#define horizontal	1
#define diagonal	2
#define vertical	3

struct move {
	int row;
	int col;
	int direction;
};

std::queue<move> q;

int n;

int map[18][18];
int visit[18][18] = { 0, };

void bfs() {
	while (!q.empty()) {
		move cur = q.front();
		q.pop();
		if (cur.direction != vertical) {
			int nextRow = cur.row;
			int nextCol = cur.col + 1;
			if (map[nextRow][nextCol] == 0) {
				visit[nextRow][nextCol]++;
				q.push({ nextRow, nextCol, horizontal });
			}
		}
		int nextRow = cur.row + 1;
		int nextCol = cur.col + 1;
		if (map[nextRow][nextCol] == 0 && map[cur.row][nextCol] == 0 && map[nextRow][cur.col] == 0) {
			visit[nextRow][nextCol]++;
			q.push({ nextRow, nextCol, diagonal });
		}
		if (cur.direction != horizontal) {
			int nextRow = cur.row + 1;
			int nextCol = cur.col;
			if (map[nextRow][nextCol] == 0) {
				visit[nextRow][nextCol]++;
				q.push({ nextRow, nextCol, vertical });
			}
		}
	}
}

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

	std::cin >> n;

	for (int row = 0; row <= n + 1; row++) {
		for (int col = 0; col <= n + 1; col++) {
			map[row][col] = 1;
		}
	}

	for (int row = 1; row <= n; row++) {
		for (int col = 1; col <= n; col++) {
			std::cin >> map[row][col];
		}
	}

	q.push({ 1, 2, horizontal });
	visit[1][2] = 1;
	bfs();

	std::cout << visit[n][n];
}

하지만 문제는 너무 느리다는 것이다. 심지어 문제 분류는 DP인데, DP는 전혀 사용하지 않았다. 분명 다른 해결 방법이 있을 것이다.

· 최종 아이디어(DP, 0ms)

이번 문제의 규칙을 다시 살펴보면서 깨달은 것은, 2차원 배열을 차례대로 탐색하는 방향과 파이프가 연결될 수 있는 방향이 일치한다는 것이다. 여기서 DP를 활용할 수 있겠다고 생각했다.

문제의 규칙 덕분에 배열의 특정 좌표를 방문할 때 해당 좌표의 좌, 좌상, 상 방향은 반드시 이미 탐색을 마친 상태이다. 이미 해당 좌표를 탐색하였는데 그곳을 경유하는 또다른 경로가 추가되었다고 뒤늦게 밝혀질 일이 없다. 따라서 2차원 배열의 각 원소를 한 번씩만 방문하면 도착점까지 도달하는 경우의 수를 충분히 알 수 있다.

중요한 것은 앞서 설명한 2번 조건 즉, 90도로 파이프의 방향을 변경할 수 없다는 것이다. 그렇다면 이전 좌표를 어떤 방향으로 방문했는지 알아야 이번 좌표를 방문할 때 어떤 방향을 배제할지 결정할 수 있다. 이는 배열에 한 차원을 추가해주었다.

dp[row][col][dir]

과 같이 선언하여 dir에 우, 우하, 하 방향으로 진입하는 경우의 수로 설정했다. 특정 좌표에서 세 가지 방향으로 이동하는 경우의 수는 다음과 같이 구할 수 있다.

• 우측 방향 : 현재 좌표에 우측으로 진입한 경우의 수 + 현재 좌표에 대각으로 진입한 경우의 수
• 대각 방향 : 현재 좌표에 우측으로 진입한 경우의 수 + 현재 좌표에 대각으로 진입한 경우의 수 + 현재 좌표에 하단으로 진입한 경우의 수
• 하단 방향 : 현재 좌표에 대각으로 진입한 경우의 수 + 현재 좌표에 하단으로 진입한 경우의 수

이것을 변수로 표현하면 다음과 같다.

dp[row][col + 1][RIGHT] += dp[row][col][RIGHT] + dp[row][col][DIAGONAL];
dp[row + 1][col + 1][DIAGONAL] += dp[row][col][RIGHT] + dp[row][col][DIAGONAL] + dp[row][col][DOWN];
dp[row + 1][col][DOWN] += dp[row][col][DIAGONAL] + dp[row][col][DOWN];

위는 이동할 수 있는 세 좌표가 모두 열려있을 때의 경우이고, 하나 이상의 좌표가 닫혀 대각선으로 이동할 수 없을 땐 우, 하 방향으로만 이동하는 경우도 고려해야 한다.

이것을 적용한 코드 전문은 아래와 같다.

// DP를 활용한 코드

#include <iostream>
#define RIGHT 0
#define DIAGONAL 1
#define DOWN 2

int map[18][18];
int dp[18][18][3] = { 0, };

int n;

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

	std::cin >> n;

	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			std::cin >> map[row][col];
		}
	}
	dp[0][1][RIGHT] = 1;
	for (int row = 0; row < n; row++) {
		int col = 0;
		if (row == 0) {
			col = 1;
		}

		for (; col < n; col++) {
        	// 대각선 방향이 열린 경우
			if (map[row][col + 1] == 0 && map[row + 1][col + 1] == 0 && map[row + 1][col] == 0) {
				dp[row][col + 1][RIGHT] += dp[row][col][RIGHT] + dp[row][col][DIAGONAL];
				dp[row + 1][col + 1][DIAGONAL] += dp[row][col][RIGHT] + dp[row][col][DIAGONAL] + dp[row][col][DOWN];
				dp[row + 1][col][DOWN] += dp[row][col][DIAGONAL] + dp[row][col][DOWN];
				continue;
			}
            // 우측 방향만 열린 경우
			if (map[row][col + 1] == 0) {
				dp[row][col + 1][RIGHT] += dp[row][col][DIAGONAL] + dp[row][col][RIGHT];
			}
            // 하단 방향만 열린 경우
			if (map[row + 1][col] == 0) {
				dp[row + 1][col][DOWN] += dp[row][col][DIAGONAL] + dp[row][col][DOWN];
			}
		}
	}
	std::cout << dp[n][n][DIAGONAL] + dp[n][n][RIGHT] + dp[n][n][DOWN];
}