[백준 17070: 파이프 옮기기 1] (C++)

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ파이프 옮기기 1

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

 

 

l 문제

 

1. 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸(r, c)은 1부터 시작하며 빈 칸이거나 벽이다. 빈 칸은 0, 벽은 1로 주어진다.

2. 집 수리를 위해서 파이프 하나를 밀어서 이동시키려고 한다. 파이프는 →, ↘, ↓ 방향으로 밀 수 있다. 파이프는 밀면서 45도 까지 회전시킬 수 있으며, (→, ↘, ↓) 3가지 방향이 가능하다.

3. 놓여진 방향에 따라 이동 방법은 다음과 같다. 가로 : →, ↘ 세로 : ↘, ↓ 대각선 : →, ↘, ↓

4. 파이프를 놓을 때 색칠된 부분은 반드시 빈 칸( 0 )이어야 한다. 하나의 파이프는 2개의 연속된 칸을 차지한다. 가장 처음에 파이프는 ( 1, 1 )와 ( 1, 2 )를 차지하고 있고, 방향은 가로이다. ( 1, 1 )와 ( 1, 2 )는 빈 칸이다.

 

 

l 연산 순서

 

1. 모든 진행 가능한 방향으로 파이프를 민다.

2. 파이프가 ( N, N ) 위치에 도달하면 Count 증가

 

 

l 예시

 

시작 모습	3 P P 0 0 0 0 0 0 0
대각선	3 P P 0 0 0 P 0 0 0
아래	3 P P 0 0 0 P 0 0 P

 

 

l 입력

 

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다.

둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

 

 

l 출력

 

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

 

 

l 풀이

 

DFS로 풀 수 있다.

DFS 함수 {    for (가능한 방향들)    {       1. 범위 조건 검사       2. 파이프를 놓는다.    } }

방향에 따라 놓을 수 있는 모든 방향으로 파이프를 계속 놓으면서 탐색 일일이 switch나 if문을 써서 제어하는 것 보다 전역으로 가능한 방향을 미리 선언해두면 쉽고 깔끔하게 코드를 작성할 수 있다.

 

 

l  코드

 

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

int N, home[17][17], ans;
int dx[] = { 0,1,1 };
int dy[] = { 1,0,1 };
vector<int> action[3] = { {0,2}, {1,2}, {0,1,2} };

// type 0 : 가로, 1 : 세로, 2 : 대각
void recur(int x, int y, int type)
{
	for (auto &t : action[type])
	{
		int tx = x + dx[t];
		int ty = y + dy[t];

		if (tx < 1 || ty < 1 || tx > N || ty > N || home[tx][ty])
			continue;

		if (t == 2 && (home[tx - 1][ty] || home[tx][ty - 1]))
			continue;

		if (tx == N && ty == N)
		{
			++ans;
			continue;
		}

		recur(tx, ty, t);
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	register int i, j;
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			cin >> home[i][j];

	if(!home[N][N]) recur(1, 2, 0);

	cout << ans;
	return 0;
}