[백준][C++]17070 - 파이프 옮기기 1

문제

• 17070번 : 파이프 옮기기
• Rank : Gold V
• 링크 : https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

풀이 전략

• 파이프는 좌, 하단, 좌하단대각선으로만 움직인다.
  • 파이프라인이 재귀될 염려가 없으므로, 파이프 이동선을 기억할 필요는 없다.
• 모든 경우의 수를 탐색하여, 가능한 경우의 수를 합산한다.

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

• 이 때, 같은 위치의 파이프 설치여부를 여러번 체크하게 되므로, 다이나믹 프로그래밍으로 풀이한다.
  • enum을 사용하여 각 상태를 정의해둔 후, 비트연산자 배열에 저장한다.
  • 타설가능 파이프 외에 검사했는지 여부를 확인하게 하여, 타설불가능 지역을 계속해서 체크하는 것을 방지한다.

int checkMap[16][16] = { 0, };
enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};
//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

 

전체 소스 코드

//Backjoon Problem No.17070
//Mist16, 2022-01-22

#include <iostream>

using namespace std;

enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};

int pipeMap[16][16] = { 0, };
int checkMap[16][16] = { 0, };
int N = 0;



//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input n, pipemap;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> pipeMap[i][j];
		}
	}
	cout << installPipe(0, 1, pipeCond::Left);

	return 0;
}

 

여담

• 골드 하위권 문제까지는 빠르게 풀 수 있는 거 같다. 고난이도 문제에 도전해볼 것.