12 min to read

PS 풀이 - BOJ 17070 파이프 옮기기 1

백준 17070번 문제 풀이 포스팅

Featured image

문제 소개

BOJ 17070 파이프 옮기기 1 썸네일에 나와있듯, 골드 5 문제이며, solved.ac 기준으로, 클래스 4에 수록되어 있는 문제입니다. 저번 게시글에서 다룬 17144번 문제와는 다르게 두가지 방법의 풀이방법을 다룰것인데, “머리가 나쁘면 몸이 고생한다” 라는 교훈을 일깨워준 좋은 문제였던것 같습니다.

문제의 상황

  1. 최소 3 \(\times\) 3 에서, 최대 16 \(\times\) 16 크기의 정사각형 배열이 주어진다는 사실
  2. 파이프가 2개의 연속된 칸을 차지하는 크기이며, 방향은 가로, 세로, 우측아래 대각선이 가능
  3. 파이프를 옮길 수 있는 방법, 그리고 옮길 때, 비어있어야 하는 칸에 대한 정보. (아래 그림에서 색칠된 칸이 비어 있어야 하는 칸들을 나타낸다) 가로로 놓인 파이프를 옮길 수 있는 방법 세로로 놓인 파이프를 옮길 수 있는 방법 대각선으로 놓인 파이프를 옮길 수 있는 방법
  4. 파이프는 빈칸만을 차지하고 있어야 한다는 조건
  5. 파이프의 시작 위치는 (1,1), (1,2)이고, 파이프의 한쪽 끝을 오른쪽 구석으로 옮겨야 한다.

문제의 조건(입력, 제한시간)

방의 가로, 세로 길이 N이 주어지고, 그 밑의 N 줄에는 방의 상태가 주어진다. 0은 빈칸, 1은 빈칸이 아닌 칸이다. \($(3 \le N \le 16)\)$ 또, (1,1), (1,2)는 항상 빈칸이다

제한시간은 1초, 메모리 제한은 512MB 이다.

맨처음 한 구현

우선 전의 포스팅에서 언급한 것처럼, 단순 구현으로 풀 수 있는 문제인가를 먼저 생각해 보았다.

최악의 상황을 가정하자면, 방의 크기가 16 \(\times\) 16일 때, 파이프의 한쪽 끝이 있을 방법은 16 \(\times\) 16 \(=\) 256 보다 적을것이고(가장자리 쪽에 있는 경우의 수는 몇가지가 불가능하다. 아예 칸 밖으로 나갈수가 없으니), 위와 비슷한 이유로, 가능한 방향도 3가지이긴 한데, 3가지가 다 안되는 경우도 많을 것이다. 또 위의 문제 상황에서 DFS나 BFS 등으로 탐색하면서, 예전에 있던 상태공간으로 다시 돌아올 일도 없다. 파이프가 움직이는 방향은, 오른쪽, 아래, 오른쪽 아래 대각선 뿐이기 때문이다. \(256 \times 3 = 768\)이니, 1초안에 연산은 다 되겠다 하여, 위의 문제 상황을 시뮬레이팅 하듯이 그대로 코드로 옮겨보았다.

#include<iostream>
#include<utility>
#include<queue>

using namespace std;

std::pair<int, int> operator +(const std::pair<int, int>& x, const std::pair<int, int>& y) {
    return std::make_pair(x.first + y.first, x.second + y.second);
}

typedef struct{
	int direction;
	pair<int,int> first, second;
}position;

pair<int,int> wayToGo[3][3][2];
vector<pair<int,int> >wayToClean[3][3];
int N;
int state[16][16];
position pipe{0,make_pair(0,0),make_pair(0,1)};
vector<pair<int,int> > diag{make_pair(0,1),make_pair(1,0),make_pair(1,1)};
queue<position> q;
pair<int,int> goal;

void preset();
bool isEmpty(pair<int,int> p);
bool canMove(position p, int way);
position movePipe(position p, int way);

int main(void){//좌표 순서는 row,col이다.
	int ret = 0;
	preset();
	cin >> N;
	goal = make_pair(N-1,N-1);
	for(int i = 0; i < N;++i)
		for(int j = 0; j < N;++j)
			cin >> state[i][j];

	q.push(pipe);
	while(!q.empty()){
		position p = q.front();
		q.pop();
		if(p.first == goal || p.second == goal){
			ret++;
			continue;
		}
		if(p.direction == 2){
			for(int i = 0; i < 3; ++i){
				if(canMove(p,i))
					q.push(movePipe(p,i));
			}
		}
		else{
			for(int i = 0; i < 2; ++i){
				if(canMove(p,i))
					q.push(movePipe(p,i));
			}
		}
	}
	cout << ret;
	return 0;
}

void preset(){
	pipe.first = make_pair(0,0); pipe.second = make_pair(0,1);

	wayToGo[0][0][0] = wayToGo[0][0][1] = make_pair(0,1);
	wayToClean[0][0].push_back(make_pair(0,1));

	wayToGo[0][1][0] = make_pair(0,1);
	wayToGo[0][1][1] = make_pair(1,1);
	wayToClean[0][1] = diag;

	wayToGo[1][0][0] = wayToGo[1][0][1] = make_pair(1,0);
	wayToClean[1][0].push_back(make_pair(1,0));

	wayToGo[1][1][0] = make_pair(1,0);
	wayToGo[1][1][1] = make_pair(1,1);
	wayToClean[1][1] = diag;

	wayToGo[2][0][0] = make_pair(1,1);
	wayToGo[2][0][1] = make_pair(0,1);
	wayToClean[2][0].push_back(make_pair(0,1));

	wayToGo[2][1][0] = make_pair(1,1);
	wayToGo[2][1][1] = make_pair(1,0);
	wayToClean[2][1].push_back(make_pair(1,0));

	wayToGo[2][2][0] = wayToGo[2][2][1] = make_pair(1,1);
	wayToClean[2][2] = diag;
}

bool isEmpty(pair<int,int> p){
	int row = p.first;
	int col = p.second;
	if(row < 0 || row >= N || col < 0 || col >= N) return false;
	return state[row][col] == 0;
}

bool canMove(position p, int way){
	for(int i = 0 ;i < wayToClean[p.direction][way].size();++i){
		if(!isEmpty(p.second+wayToClean[p.direction][way][i])) return false;
	}

	return isEmpty(p.first+wayToGo[p.direction][way][0])
    && isEmpty(p.second+wayToGo[p.direction][way][1]);
}

position movePipe(position p, int way){
	position ret{p.direction,p.first+wayToGo[p.direction][way][0],
    p.second+wayToGo[p.direction][way][1]};
	if(p.direction < 2 && way == 1) ret.direction = 2;
	else if(p.direction == 2) ret.direction = way;
	return ret;
}

파이프의 위치를 나타내는 구조체를 만들고, 파이프의 움직임을 제약하는 사항들을 모두 변수 등으로 기록하여서 움직이게 하였다. 이 방법은 코드가 길어지기 때문에 상당한 노력을 필요로 하였고, 1초라는 제한시간에 만족하였지만, 위 문제와 상황은 같은데, 방 크기 제한이 32까지로 늘어난 파이프 옮기기 2라는 문제에서는 도저히 시간 내에 풀 수 없었다.

옆동네에서 머리를 탁 치며 가져온 DP

구현 문제를 풀었다는 뿌듯함에 평소처럼 다른 사람들의 코드를 읽어봤던 본인은 다른 사람들의 코드 길이에 경악을 금치 않을 수 없었다. 나는 140줄에 짰는데, 숏코딩으로 가독성을 포기한 코드가 아닌데도, 20줄 가량의 코드가 정답 판정을, 그것도 더 빠르게 받는 것이었다.

타인의 코드를 찬찬히 읽어보고 깨달았다. 이 문제가 고등학교때 확률과 통계 과목에서 다루었던, 길찾기 문제(위 글에서 덧셈을 이용해 푸는 방법의 핵심 아이디어)와 크게 다를 바 없다는 것을. 그냥 몇몇가지 조건을 반영 잘 시키면 된다는 것을.

#include<iostream>

int N, map[17][17] = {}, dp[3][17][17] = {};

using namespace std;

bool check(int x, int y) {
	if (1 <= x && x <= N && 1 <= y && y <= N && map[x][y] == 0)
		return true;
	return false;
}

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

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	dp[0][1][2] = 1;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++) {
			if (check(i, j - 1) && check(i, j))
				dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];
			if (check(i - 1, j) && check(i, j))
				dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];
			if (check(i - 1, j - 1) && check(i - 1, j) && check(i, j - 1) && check(i, j))
				dp[2][i][j] += dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
		}
	}
	cout << dp[0][N][N] + dp[1][N][N] + dp[2][N][N];

	return 0;
}

출처 : https://travelbeeee.tistory.com/277

위 코드에서는 dp라는 배열을 추가로 사용하는데, 인덱스의 의미는 다음과 같다 [파이프의 방향] [파이프 끝의 행 좌표] [파이프 끝의 열 좌표]

(파이프의 방향 : 가로 0, 세로 1, 대각 2)

그러므로 시작할 때, 파이프의 한쪽 끝이 (1,2)에 있으니 이걸 배열에 반영시켜 주고, 각 칸을 순회하면서, 이동하기에 충분한 칸이 비어 있으면, 위의 길찾기 문제 풀듯이 인접한 칸으로 갈 수 있는 경우의 수를 더해가며 문제를 해결한다.