BOJ 15684 : 사다리 조작 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/15684

 

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

먼저, 사다리를 구성하는 MAP 주변을 벽(3)으로 만들자.

그리고 사다리 설치는 1 → 2로 설치하자.

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

	for (int r = 0; r <= H + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 3; /* 벽 설치 */

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

	for (int i = 0; i < M; i++)
	{
		int r, c;

		scanf("%d %d", &r, &c);

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

	return;
}

이렇게 사다리를 설치하면, MAP에서 1을 만날 때 2로 이동, 2를 만나면 1로 이동할 수 있다.

 

이제 사다리 게임을 진행해서 모두 그대로 내려오는지 check하는 함수를 만들자.

 

1) 1번 사다리는 MAP[1][1]에서, N번 사다리는 MAP[1][N]에서 출발한다.

2) 그리고 MAP[r][c]가 0이면 한칸 내려가고 (MAP[r][c]에서 r의 증가)

3) MAP[r][c]가 1이면 오른쪽으로 이동 후 아래로 내려간다. (r, c의 증가)

4) 반대로 2면, 왼쪽으로 이동 후 아래로 내려간다. (r 증가, c 감소)

 

최종적으로 r이 H + 1이 되면 종료이고 이때, c가 사다리 번호와 같다면 pass가 된다.

전체 사다리가 모두 통과해야하므로 for문을 이용해 아래와 같이 만들 수 있다.

int check()
{
	for (int ladder = 1; ladder <= N; ladder++)
	{
		int sr, sc;

		sr = 1;
		sc = ladder;

		while (1)
		{
			if (sr == H + 1) break;

			if (MAP[sr][sc] == 0) sr++;
			else
			{
				if (MAP[sr][sc + 1] == 1) sc++, sr++;
				else sc--, sr++;
			}
		}

		printf("ladder : %d / end %d\n", ladder, sc);
	}

	return 1;
}

실제 input을 입력받아 디버깅을 해보자.

 

아래의 예시 처럼 1 → 3 / 2 → 2 / 3 → 5 / 4 → 1 / 5 → 4로 가는 것을 알 수 있다.

디버깅으로 제대로 동작하는 것을 확인했으니,

ladder와 도착점이 다른 경우 return 0을, 모두 정상 도착했을 경우 return 1을 하도록 수정하자.

int check()
{
	for (int ladder = 1; ladder <= N; ladder++)
	{
		...
        
		while (1) { ... }

		if (ladder != sc) return 0;
	}

	return 1;
}

 

이제 사다리를 최대 3개까지 설치해보자.

사다리 설치는 기출문제 연구소의 벽 설치의 코드와 비슷하다.

두 가로선이 연속하거나 서로 접하면 안되므로 continue 조건이 바뀐다.

void DFS(int L, int sr)
{

	if( L > 3 ) { return; }

	for (int r = sr; r <= H; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1 || MAP[r][c] == 2
				|| MAP[r][c + 1] == 1 || MAP[r][c + 1] == 3) continue;

			/* 사다리 설치 */
			MAP[r][c] = 1;
			MAP[r][c + 1] = 2;

			DFS(L + 1, r, max);

			/* 사다리 설치 해제 */
			MAP[r][c] = 0;
			MAP[r][c + 1] = 0;
		}
	}
}

현재의 MAP에 이미 사다리가 설치된 경우는 설치하지 않는다. (MAP[r][c] == 1 || MAP[r][c] == 2)

그리고 MAP의 옆 칸이 사다리가 있거나, 벽인 경우도 설치할 수 없다. (MAP[r][c + 1] == 1 || MAP[r][c + 1] == 3)

 

그 외에는 현재 칸을 1로, 다음 칸을 2로 해서 사다리를 설치한다.

그리고 3개 까지 사다리를 설치할 수 있으므로 종료 조건은 (L > 3)이 된다.

 

하지만 이 경우에 문제가 생긴다.

사다리를 1개만 설치해도 사다리 게임을 통과하는 경우를 가정해보자.

 

현재 코드대로 라면, DFS에 의해

 

1개 설치 -> 2개 설치 -> 3개 설치 -> 다음 3개 설치 -> ... -> 3개 설치 종료.

1개 설치 -> 새로운 2번째 사다리 설치 -> 3개 설치 -> 다음 3개 설치 ... -> 3개 설치 종료.

...

새로운 1개 설치 -> 2개 설치 -> ... -> 3개 설치 종료.

...

 

와 같은 방식으로 사다리를 설치하게 되고, 1개에 답이 있음에도 불구하고, 2개 설치와 3개 설치를 병행해야 한다.

 

따라서 DFS에 최대 몇 개까지 설치할지 정하는 값을 넘겨서

1개를 모두 설치한 후, 답이 없으면 2개 설치, 이후 답이 없으면 3개 설치를 하도록 설계하자.

int PASS = 0;
void DFS(int L, int sr, int max)
{

	if (L == max) /* 최대 max까지 설치 후 check */
	{
		if (check()) PASS = 1;
		return;
	}

	for (int r = sr; r <= H; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1 || MAP[r][c] == 2 
				|| MAP[r][c + 1] == 1 || MAP[r][c + 1] == 3) continue;

			MAP[r][c] = 1;
			MAP[r][c + 1] = 2;

			DFS(L + 1, r, max);

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

 

DFS에 최대 설치 갯수를 정했으므로, 사다리 설치 0 ~ 3 까지 설치한 후, check하면 된다.

도중에 check가 1로 리턴되면 PASS = 1로 변경하여 답을 출력하고, 모두 pass하지 못했다면 -1을 출력하면 된다.

if (check()) /* 사다리 설치가 필요 없는 경우 */
{
	printf("0\n");
	return 0;
}
	
for (int setup = 1; setup <= 3; setup++)
{
	DFS(0, 1, setup);

	if (PASS)
	{
		printf("%d\n", setup); /* 1개 설치 ~ 3개 설치 순서대로 진행 */
		return 0;
	}
}

printf("-1\n");

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

int N, M, H;

int MAP[30 + 5][10 + 5];

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

	for (int r = 0; r <= H + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 3; /* 벽 설치 */

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

	for (int i = 0; i < M; i++)
	{
		int r, c;

		scanf("%d %d", &r, &c);

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

	return;
}

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

int check()
{
	for (int ladder = 1; ladder <= N; ladder++)
	{
		int sr, sc;

		sr = 1;
		sc = ladder;

		while (1)
		{
			if (sr == H + 1) break;

			if (MAP[sr][sc] == 0) sr++;
			else
			{
				if (MAP[sr][sc] == 1) sc++, sr++;
				else sc--, sr++;
			}
		}

		if (ladder != sc) return 0;
	}

	return 1;
}

int PASS = 0;
void DFS(int L, int sr, int max)
{
	if (L == max)
	{
		// output();
		if (check()) PASS = 1;
		return;
	}

	for (int r = sr; r <= H; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1 || MAP[r][c] == 2 
				|| MAP[r][c + 1] == 1 || MAP[r][c + 1] == 3) continue;

			MAP[r][c] = 1;
			MAP[r][c + 1] = 2;

			DFS(L + 1, r, max);

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

int main(void)
{
	int sr, sc;

	input();

	if (check()) /* 사다리 설치가 필요 없는 경우 */
	{
		printf("0\n");
		return 0;
	}
	
	for (int setup = 1; setup <= 3; setup++)
	{
		DFS(0, 1, setup);

		if (PASS)
		{
			printf("%d\n", setup);
			return 0;
		}
	}

	printf("-1\n");

	return 0;
}

 

A형의 tc는 여러 개이므로 PASS = 0을 초기화하는 것을 잊지 말자.