글 읽기 - [C] 백트래킹문제 질문드립니다.

lokilo 4년 전 0

범위에 문제 형식은 재귀함수를 이용한 백트래킹 문제로 판단하고 접근했습니다.

직접 X번째 조각이 들어 갈 수 있는지 확인하여 직접 채워넣고 빼는 방식으로 해서 다 해보는 방식으로 접근했습니다.

사전 순으로 먼저 오는 것을 출력하라는 조건은 1번 조각부터 먼저 넣고 2,3,4,5 조각을 넣는다고 했을 때 가장 먼저 완성되는 형태가 사전순으로 우위라고 판단하였습니다.

gg를 출력(불가능) 하는 조건
-> 1) 마지막 조각까지 채워 넣을 수 없음
2) 다 채워넣었으나 빈공간이 남아있는 경우

알고리즘 특성 상 모든 경우를 다 해보는 것 일텐데 왜 안나오는지 상당히 머리가 아픕니다. ㅠ

제 생각으로 제작할 수 있는 데이터는 전부 예상대로 나왔는데 어떠한 부분에서 WA가 뜨는지 모르겠어서 도움을 요청합니다.

소스코드는 위와 같으며 주석을 달아 놓았습니다.

#include <stdio.h>

int map[12][12];
int piece[5][12][12];
int piecex[5];
int piecey[5];
int L;

bool can_in(int X, int x, int y) //X번째 조각을 넣을 수 있는지
{
	int i, j;
	int a, b;

	if (x + piecex[X]-1 <= L && y + piecey[X]-1 <= L)
	{
		for (i = x, a= 1; i <= x + piecex[X]-1; i++,a++)
		{
			for (j = y, b=1; j <= y + piecey[X]-1; j++,b++)
			{
				if (piece[X][a][b] != 0)
				{
					if(map[i][j] != 0)
						return false;
				}
			}
		}
	}
	else
		return false;

	return true;
}

void fill_in(int X, int x, int y) //X번째 조각 넣기
{
	int i, j;
	int a, b;

	for (i = x, a=1; i <= x + piecex[X]-1; i++,a++)
	{
		for (j = y,b=1; j <= y + piecey[X]-1; j++,b++)
		{
			if(piece[X][a][b] != 0)
				map[i][j] = piece[X][a][b];
		}
	}

	return;
}

void pull_out(int X, int x, int y) //X번째 조각 빼기
{
	int i, j;
	int a, b;
	for (i = x, a=1; i <= x + piecex[X]-1; i++,a++)
	{
		for (j = y,b=1; j <= y + piecey[X]-1; j++,b++)
		{
			if (piece[X][a][b] != 0)
				map[i][j] = 0;
		}
	}
	return;
}

int out_sw = 0;
void print_ans()
{
	int i, j;

	for (i = 1; i <= L; i++)
		for (j = 1; j <= L; j++)
			if (map[i][j] == 0)  // 모든 조각을 넣고 빈공간이 남은 상황
			{
				out_sw = -1;
				return;
			}
	for (i = 1; i <= L; i++)
	{
		for (j = 1; j <= L; j++)
		{
			printf("%d", map[i][j]);
		}
		printf("\n");
	}
}

void debug() //디버깅용
{
	int i, j;

	for (i = 1; i <= L; i++)
	{
		for (j = 1; j <= L; j++)
		{
			printf("%d", map[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void dfs(int X)
{
	int i, j;

	for (i = 1; i <= L; i++)
	{
		for (j = 1; j <= L; j++)
		{
			if (can_in(X, i, j)) //X번째 조각이 들어갈 수 있는 상황인지?
			{
				fill_in(X, i, j);  //X번째 조각 채워넣기
//				debug();
				if (X == 4) // 마지막 조각까지 다 채워 넣었다면...
				{
					print_ans();
					if(out_sw != -1)
						out_sw = 1;

					return;
				}
				dfs(X + 1); //다음 조각
				if (out_sw == 1 || out_sw == -1) // 1-> 성공, -1 -> 빈칸있음
					return;

				pull_out(X, i, j); //X번째 조각 빼내기
			}
		}
	}
}
int main()
{
//	freopen("input.txt", "r", stdin);

	scanf("%d", &L);
	int I;
	int i, j;
	for (I = 0; I < 5; I++)
	{	
		scanf("%d %d\n", &piecex[I], &piecey[I]);
		
		for (i = 1; i <= piecex[I]; i++)
		{
			for (j = 1; j <= piecey[I]; j++)
			{
				char t;
				scanf("%c", &t);
				if (t == '#')
					piece[I][i][j] = I + 1;
				else
					piece[I][i][j] = 0;
			}
			scanf("\n");
		}
	}

	dfs(0);

	if (out_sw == 0 || out_sw == -1)
		printf("gg");
}

lsujj48 3년 전 1

51111

11111

22222

이게

22222

51111

11111

보다 빨리완성되더라구요..

lokilo 3년 전 0

사전순으로 앞서는 경우가 생기는 반례가 있었군요

고맙습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C] 백트래킹문제 질문드립니다.

lokilo 4년 전 0

lsujj48 3년 전 1

lokilo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말