[백준17070] 파이프 옮기기1

문제 출처: https://www.acmicpc.net/problem/17070

풀이

주어진조건을 이용하여 모든 가능한 경우를 탐색하는 완전탐색 문제입니다.

파이프가 가로방향일 때는 오른쪽과 대각선, 세로방향일 때는 세로방향과 대각선, 대각선 방향일 때는 오른쪽+대각선+세로 모두 이동가능합니다.

이 조건을 이용하여 중요한 부분들을 적어보았습니다.

1. 방향배열(dx,dy)의 요소는 4개가 아니라 3개입니다.(서쪽방향이없음)

2. 파이프끝의 좌표와 현재 방향을 시작으로 dfs연산을 합니다.

3. dfs내부에서 y==n-1&&x==n-1이면 파이프가 끝에 도착한것이므로 경우의수를++해주고 종료합니다.

4. 파이프가 움직일 수 있는 경우에 대해서만 연산 할 수 있게 코드를 작성합니다.

문제에서 주어진 조건 순서대로 파이프가 가로방향일 때, 세로방향일 때, 대각선 방향일 때 움직일 수 있는 경우만 계산합니다.

중요한것은, 대각선 방향일 때, 파이프가 동쪽,남쪽,대각선방향 3칸을 차지하므로, 동쪽,남쪽방향이 벽일 때를 고려해줘야합니다. 

(대각선 방향일 때는 ny,nx로 다음 방향들을 탐색 할 때 if(map[ny][nx]!=1)의 조건에의해 검사됩니다.)

그리고, 구현할 때 굳이 파이프의 방향변수를 선언하여 걍 방향별로 연산을하는 번거로운 코드들을 작성하지않아도됩니다.

왜냐하면 dfs함수 내부에서 한번 연산 할 때 방향별로(동,대각,아래) 한번 씩 수행되기 때문에, 방향별로 탐색하는 for문의 i가 파이프의 방향을 나타내기도 하기 때문입니다. 

만약 pipe변수를 선언하여 0(동쪽)일때, 1(대각선), 2(아래)에 대해 각각 계산하고자 했다면 코드가 길어졌을겁니다. 

코드

#include<iostream>
using namespace std;
int n;
int map[16][16];
//동 대각선,아래
int dx[3] = { 1,1,0 };
int dy[3] = { 0,1,1 };
//파이프방향
int ans;
void dfs(int y, int x, int dir);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	///3번쨰 인자는 파이프방향임(0:동:1:대각2:남)
	dfs(0, 1, 0);
	cout << ans << '\n';
}
void dfs(int y, int x, int dir)
{
	if (y == n - 1 && x == n - 1)
	{
		ans++;
		return;
	}
	//3방향에대해 검색
	for (int i = 0; i < 3; i++)
	{
		//파이프가 가로면 가로+대각선만계산
		if (dir == 0 && i == 2)continue;
		//파이프가 세로면 세로+대각선만계산
		if (dir == 2 && i == 0)continue;
		//대각선일 때
		if (i == 1 && (map[y][x + 1] == 1 || map[y + 1][x] == 1))
			continue;

		int ny = y + dy[i];
		int nx = x + dx[i];
		//범위벗어나지않고 이동한 좌표가벽아닐 때
		if (ny < n && nx < n && map[ny][nx] != 1)
			dfs(ny, nx, i);
	}
}

결과