BOJ 17070 : 파이프 옮기기 1 (A형 상시)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

www.acmicpc.net/problem/17070

 

 

이후 설명 및 입/출력은 링크 참고

 

파이프는 오른쪽, 아래, 대각선으로만 진행하므로 방향을 3개 define한다.

input에서는 MAP 주변에 벽을 세운다.

#define MAX (16 + 5)

#define RIGHT (0)
#define DOWN (1)
#define RIGHT_DOWN (2)

int N;
int MAP[MAX][MAX];

void input()
{
	scanf("%d", &N);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

 

(1, 1)과 (1, 2)에 항상 파이프가 가로로 시작하므로,

MAP[1][1]과 MAP[1][2]에 파이프를 설치하고, DFS는 (1, 2), RIGHT로 시작한다.

int main(void)
{
	input();

	MAP[1][1] = 1;
	MAP[1][2] = 1;

	DFS(1, 2, RIGHT);

	printf("%d\n", ANS_COUNT);

	return 0;
}

---

가로 파이프의 다음에는 가로나 대각선의 파이프만 올 수 있다.

 

따라서 (r, c)를 기준으로 MAP[r][c + 1]이 0이면 RIGHT를 보낸다.

MAP[r + 1][c], MAP[r][c + 1], MAP[r + 1][c + 1]이 모두 0이면 대각선으로 DFS를 진행한다.

if (MAP[r][c + 1] == 0 && dir == RIGHT)
{
	MAP[r][c + 1] = 1;

	DFS(r, c + 1, RIGHT);

	MAP[r][c + 1] = 0;
}

if (MAP[r + 1][c] + MAP[r][c + 1] + MAP[r + 1][c + 1] == 0 && dir == RIGHT)
{
	MAP[r + 1][c] = 1;
	MAP[r][c + 1] = 1;
	MAP[r + 1][c + 1] = 1;

	DFS(r + 1, c + 1, RIGHT_DOWN);

	MAP[r + 1][c] = 0;
	MAP[r][c + 1] = 0;
	MAP[r + 1][c + 1] = 0;
}

---

세로 파이프 다음에는 세로와 대각선이 가능하다.

 

따라서 (r, c)를 기준으로 MAP[r + 1][c]이 0이면 DOWN을 보낸다.

MAP[r + 1][c], MAP[r][c + 1], MAP[r + 1][c + 1]이 모두 0이면 대각선으로 DFS를 진행한다.

if (MAP[r + 1][c] == 0 && dir == DOWN)
{
	MAP[r + 1][c] = 1;

	DFS(r + 1, c, DOWN);

	MAP[r + 1][c] = 0;
}

if (MAP[r + 1][c] + MAP[r][c + 1] + MAP[r + 1][c + 1] == 0 && dir == DOWN)
{
	MAP[r + 1][c] = 1;
	MAP[r][c + 1] = 1;
	MAP[r + 1][c + 1] = 1;

	DFS(r + 1, c + 1, RIGHT_DOWN);

	MAP[r + 1][c] = 0;
	MAP[r][c + 1] = 0;
	MAP[r + 1][c + 1] = 0;
}

---

대각선 파이프의 경우 모든 경우가 가능하다.

 

따라서 (r, c)를 기준으로 옆과 아래를 체크하여 RIGHT 또는 DOWN을 보낸다.

MAP[r + 1][c], MAP[r][c + 1], MAP[r + 1][c + 1]이 모두 0이면 대각선으로 DFS를 진행한다.

if (MAP[r][c + 1] == 0 && dir == RIGHT_DOWN)
{
	MAP[r][c + 1] = 1;

	DFS(r, c + 1, RIGHT);

	MAP[r][c + 1] = 0;
}

if (MAP[r + 1][c] == 0 && dir == RIGHT_DOWN)
{
	MAP[r + 1][c] = 1;

	DFS(r + 1, c, DOWN);

	MAP[r + 1][c] = 0;
}

if (MAP[r + 1][c] + MAP[r][c + 1] + MAP[r + 1][c + 1] == 0 && dir == RIGHT_DOWN)
{
	MAP[r + 1][c] = 1;
	MAP[r][c + 1] = 1;
	MAP[r + 1][c + 1] = 1;

	DFS(r + 1, c + 1, RIGHT_DOWN);

	MAP[r + 1][c] = 0;
	MAP[r][c + 1] = 0;
	MAP[r + 1][c + 1] = 0;
}

 

파이프를 설치하고 DFS가 종료되면 MAP에서 파이프를 제거해야한다.

그리고 (r, c)가 (N, N)인 경우만 COUNT를 올리면 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (16 + 5)

#define RIGHT (0)
#define DOWN (1)
#define RIGHT_DOWN (2)

int N;
int MAP[MAX][MAX];

void input()
{
	scanf("%d", &N);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

int ANS_COUNT = 0;

void DFS(int r, int c, int dir)
{
	if (r == N && c == N)
	{
		ANS_COUNT++;
		return;
	}

	if (MAP[r][c + 1] == 0 && dir == RIGHT)
	{
		MAP[r][c + 1] = 1;

		DFS(r, c + 1, RIGHT);

		MAP[r][c + 1] = 0;
	}

	if (MAP[r + 1][c] + MAP[r][c + 1] + MAP[r + 1][c + 1] == 0 && dir == RIGHT)
	{
		MAP[r + 1][c] = 1;
		MAP[r][c + 1] = 1;
		MAP[r + 1][c + 1] = 1;

		DFS(r + 1, c + 1, RIGHT_DOWN);

		MAP[r + 1][c] = 0;
		MAP[r][c + 1] = 0;
		MAP[r + 1][c + 1] = 0;
	}

	if (MAP[r + 1][c] == 0 && dir == DOWN)
	{
		MAP[r + 1][c] = 1;

		DFS(r + 1, c, DOWN);

		MAP[r + 1][c] = 0;
	}

	if (MAP[r + 1][c] + MAP[r][c + 1] + MAP[r + 1][c + 1] == 0 && dir == DOWN)
	{
		MAP[r + 1][c] = 1;
		MAP[r][c + 1] = 1;
		MAP[r + 1][c + 1] = 1;

		DFS(r + 1, c + 1, RIGHT_DOWN);

		MAP[r + 1][c] = 0;
		MAP[r][c + 1] = 0;
		MAP[r + 1][c + 1] = 0;
	}

	if (MAP[r][c + 1] == 0 && dir == RIGHT_DOWN)
	{
		MAP[r][c + 1] = 1;

		DFS(r, c + 1, RIGHT);

		MAP[r][c + 1] = 0;
	}

	if (MAP[r + 1][c] == 0 && dir == RIGHT_DOWN)
	{
		MAP[r + 1][c] = 1;

		DFS(r + 1, c, DOWN);

		MAP[r + 1][c] = 0;
	}

	if (MAP[r + 1][c] + MAP[r][c + 1] + MAP[r + 1][c + 1] == 0 && dir == RIGHT_DOWN)
	{
		MAP[r + 1][c] = 1;
		MAP[r][c + 1] = 1;
		MAP[r + 1][c + 1] = 1;

		DFS(r + 1, c + 1, RIGHT_DOWN);

		MAP[r + 1][c] = 0;
		MAP[r][c + 1] = 0;
		MAP[r + 1][c + 1] = 0;
	}
}

int main(void)
{
	input();

	MAP[1][1] = 1;
	MAP[1][2] = 1;

	DFS(1, 2, RIGHT);

	printf("%d\n", ANS_COUNT);

	return 0;
}