글 읽기 - 반례를 찾지 못하겠습니다...

qlqh0987 3년 전 0

게시판에 있는 테스트 케이스
다 확인해보진 못했어도 https://boohyunsik.github.io/exit-marble-test-case/ 여기 포함해서 150개 정도 확인해보았는데 반례를 찾지 못했습니다...

절반도 못넘기고 바로 틀렸습니다가 출력되네요..

BFS 알고리즘을 C로 구현하였고요, board_get_min_do_tilt() 함수를 호출하면 지역변수로 큐를 생성하고, 해당 큐를 이용해서 검색을 하도록 구현했습니다.

구슬 굴리는 함수는 board_do_tilt() 함수에서 구현했고요,
반복문 이용, R이랑 B 모두 안움직였거나 B가 구멍에 들어가면 큐에 저장 안되도록 하고,
큐를 POP할때 이전에 기울였던 방향정보도 같이 읽도록 해서 이전에 기울였던 방향의 수직방향으로만 기울이도록 구현했습니다..

혹시 반례나 코드 오류 발견하시면 댓글로 알려주시면 감사하겠습니다!!

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int row, col;
} marble_pos;
void marble_move(marble_pos* dst, int row, int col)
{
	dst->row = row;
	dst->col = col;
}
int marble_check_overlap(marble_pos* dst, marble_pos* src)
{
	if (dst->row == src->row && dst->col == src->col)
		return 1;
	else return 0;
}

typedef struct
{
	char** map;
	int size_row, size_col;
	marble_pos* R, * B, * O;
} marble_board;

typedef enum
{
	UP, DOWN, LEFT, RIGHT
} tilt_direction;

typedef enum
{
	TILT_DONE, TILT_SUCCESS, TILT_FAIL
} tilt_result;

int board_get_min_do_tilt(marble_board* board, const int tot_try_num);
tilt_result board_do_tilt(marble_board* board,
	marble_pos* dst_R, marble_pos* src_R, 
	marble_pos* dst_B, marble_pos* src_B, tilt_direction direction);

int main()
{
	int i, j;
	marble_board* board = (marble_board*)malloc(sizeof(marble_board));
	
	scanf("%d %d", &(board->size_row), &(board->size_col));
	if (board->size_row < 3 || board->size_col < 3)
//		|| board->size_row>10 || board->size_col>10)
	{
		free(board);
		printf("-1");
		return 0;
	}

	board->map = (char**)malloc(sizeof(char*) * board->size_row);
	for (i = 0; i < board->size_row; i++)
		board->map[i] = (char*)malloc(sizeof(char) * (board->size_col + 1));
	board->R = (marble_pos*)malloc(sizeof(marble_pos));
	board->B = (marble_pos*)malloc(sizeof(marble_pos));
	board->O = (marble_pos*)malloc(sizeof(marble_pos));

	for (i = 0;i < board->size_row; i++)
	{
		scanf("%s", board->map[i]);
		for (j = 0;j < board->size_col; j++)
		{
			if (board->map[i][j] == 'R')
			{
				marble_move(board->R, i, j);
				board->map[i][j] = '.';
			}
			else if (board->map[i][j] == 'B')
			{
				marble_move(board->B, i, j);
				board->map[i][j] = '.';
			}
			else if (board->map[i][j] == 'O')
			{
				marble_move(board->O, i, j);
				board->map[i][j] = '.';
			}
		}
	}

	printf("%d", board_get_min_do_tilt(board, 10));

	free(board->R);
	free(board->B);
	free(board->O);
	for (i = 0; i < board->size_row; i++)
		free(board->map[i]);
	free(board->map);
	free(board);
}

int board_get_min_do_tilt(marble_board* board, const int tot_try_num)
{
	const int max_queue_size = 100;
	marble_pos* queue_R, * queue_B;
	tilt_direction* queue_direction;
	int cusor_head = 0, cusor_tail = 0, queue_size = 1;
	int try_num, ret, i, tilt_result, temp_cusor_tail, temp_cusor_head, plus_queue_size, flag_find;
	int direction_int;

	if (marble_check_overlap(board->O, board->R)
		&& (!marble_check_overlap(board->O, board->B)))
		return 0;

	queue_R = (marble_pos*)malloc(sizeof(marble_pos) * max_queue_size);
	queue_B = (marble_pos*)malloc(sizeof(marble_pos) * max_queue_size);
	queue_direction = (tilt_direction*)malloc(sizeof(tilt_direction) * max_queue_size);
	ret = -1;

	queue_R[0].row = board->R->row;
	queue_R[0].col = board->R->col;
	queue_B[0].row = board->B->row;
	queue_B[0].col = board->B->col;
	queue_direction[0] = UP - RIGHT;
	
	for (try_num = 1; try_num <= tot_try_num; try_num++)
	{
		plus_queue_size = 0; flag_find = 0;
		for (i = 0; i < queue_size;i++)
		{
			temp_cusor_head = (cusor_head + i) % max_queue_size;
			for (direction_int = (int)UP; direction_int <= (int)RIGHT; direction_int++)
			{
				if ((queue_direction[temp_cusor_head] == UP || queue_direction[temp_cusor_head] == DOWN)
					&& ((tilt_direction)direction_int == UP || (tilt_direction)direction_int == DOWN)) continue;
				else if ((queue_direction[temp_cusor_head] == LEFT || queue_direction[temp_cusor_head] == RIGHT)
					&& ((tilt_direction)direction_int == LEFT || (tilt_direction)direction_int == RIGHT)) continue;

				temp_cusor_tail = (cusor_tail + 1) % max_queue_size;

				tilt_result = board_do_tilt(board, &queue_R[temp_cusor_tail], &queue_R[temp_cusor_head],
					&queue_B[temp_cusor_tail], &queue_B[temp_cusor_head], (tilt_direction)direction_int);
				if (tilt_result == TILT_DONE)
				{
					cusor_tail = temp_cusor_tail;
					queue_direction[temp_cusor_tail] = (tilt_direction)direction_int;
					plus_queue_size++;
				}
				else if (tilt_result == TILT_SUCCESS)
				{
					flag_find = 1;
					ret = try_num;
					break;
				}
			}
			if (!flag_find)
			{
				plus_queue_size--;
			}
			else break;
		}
		if (!flag_find)
		{
			cusor_head += queue_size;
			queue_size += plus_queue_size;
		}
		else break;
	}

	free(queue_B);
	free(queue_R);
	return ret;
}

tilt_result board_do_tilt(marble_board* board,
	marble_pos* dst_R, marble_pos* src_R,
	marble_pos* dst_B, marble_pos* src_B, tilt_direction direction)
{
	int R_move_num = 0, B_move_num = 0, is_changed, R_is_goal = 0;
	marble_pos temp_R, temp_B;

	temp_R.row = src_R->row; dst_R->row = temp_R.row;
	temp_R.col = src_R->col; dst_R->col = temp_R.col;
	temp_B.row = src_B->row; dst_B->row = temp_B.row;
	temp_B.col = src_B->col; dst_B->col = temp_B.col;

	switch (direction)
	{
	case UP:
		while (1)
		{
			is_changed = 0;

			temp_R.row = dst_R->row;
			while (!R_is_goal)
			{
				if (temp_R.row > 0) temp_R.row--;
				if (board->map[temp_R.row][temp_R.col] == '.')
				{
					if (marble_check_overlap(dst_B, &temp_R)) break;
					else if (marble_check_overlap(board->O, &temp_R))
					{
						R_is_goal = 1;
						dst_R->row = -1;
						dst_R->col = -1;
						break;
					}
					else
					{
						dst_R->row = temp_R.row;
						R_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			temp_B.row = dst_B->row;
			while (1)
			{
				if (temp_B.row > 0) temp_B.row--;
				if (board->map[temp_B.row][temp_B.col] == '.')
				{
					if (marble_check_overlap(dst_R, &temp_B)) break;
					else if (marble_check_overlap(board->O, &temp_B)) return TILT_FAIL;
					else
					{
						dst_B->row = temp_B.row;
						B_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			if (!is_changed) break;
		}
		break;

	case DOWN:
		while (1)
		{
			is_changed = 0;

			temp_R.row = dst_R->row;
			while (!R_is_goal)
			{
				if (temp_R.row < board->size_row - 1) temp_R.row++;
				if (board->map[temp_R.row][temp_R.col] == '.')
				{
					if (marble_check_overlap(dst_B, &temp_R)) break;
					else if (marble_check_overlap(board->O, &temp_R))
					{
						R_is_goal = 1;
						dst_R->row = -1;
						dst_R->col = -1;
						break;
					}
					else
					{
						dst_R->row = temp_R.row;
						R_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			temp_B.row = dst_B->row;
			while (1)
			{
				if (temp_B.row < board->size_row - 1) temp_B.row++;
				if (board->map[temp_B.row][temp_B.col] == '.')
				{
					if (marble_check_overlap(dst_R, &temp_B)) break;
					else if (marble_check_overlap(board->O, &temp_B)) return TILT_FAIL;
					else
					{
						dst_B->row = temp_B.row;
						B_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			if (!is_changed) break;
		}
		break;

	case LEFT:
		while (1)
		{
			is_changed = 0;

			temp_R.col = dst_R->col;
			while (!R_is_goal)
			{
				if (temp_R.col > 0) temp_R.col--;
				if (board->map[temp_R.row][temp_R.col] == '.')
				{
					if (marble_check_overlap(dst_B, &temp_R)) break;
					else if (marble_check_overlap(board->O, &temp_R))
					{
						R_is_goal = 1;
						dst_R->row = -1;
						dst_R->col = -1;
						break;
					}
					else
					{
						dst_R->col = temp_R.col;
						R_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			temp_B.col = dst_B->col;
			while (1)
			{
				if (temp_B.col > 0) temp_B.col--;
				if (board->map[temp_B.row][temp_B.col] == '.')
				{
					if (marble_check_overlap(dst_R, &temp_B)) break;
					else if (marble_check_overlap(board->O, &temp_B)) return TILT_FAIL;
					else
					{
						dst_B->col = temp_B.col;
						B_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			if (!is_changed) break;
		}
		break;

	case RIGHT:
		while (1)
		{
			is_changed = 0;

			temp_R.col = dst_R->col;
			while (!R_is_goal)
			{
				if (temp_R.col < board->size_col - 1) temp_R.col++;
				if (board->map[temp_R.row][temp_R.col] == '.')
				{
					if (marble_check_overlap(dst_B, &temp_R)) break;
					else if (marble_check_overlap(board->O, &temp_R))
					{
						R_is_goal = 1;
						dst_R->row = -1;
						dst_R->col = -1;
						break;
					}
					else
					{
						dst_R->col = temp_R.col;
						R_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			temp_B.col = dst_B->col;
			while (1)
			{
				if (temp_B.col < board->size_col - 1) temp_B.col++;
				if (board->map[temp_B.row][temp_B.col] == '.')
				{
					if (marble_check_overlap(dst_R, &temp_B)) break;
					else if (marble_check_overlap(board->O, &temp_B)) return TILT_FAIL;
					else
					{
						dst_B->col = temp_B.col;
						B_move_num++;
						is_changed = 1;
					}
				}
				else break;
			}

			if (!is_changed) break;
		}
		break;
	}

	if (R_is_goal) return TILT_SUCCESS;
	else if (!R_move_num && !B_move_num) return TILT_FAIL;
	else return TILT_DONE;
}

qlqh0987 3년 전 0

자답합니다. 코드가 너무 난잡한거 같아서 갈아엎고 다시해봤더니 풀렸습니다.

코드가 난잡하다보니 어디선가 꼬이지 않았었나 싶네요...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define	MAX_BOARD_SIZE	10
#define	MAX_NUM_TRY	10

typedef enum OBJECT
{
	EMPTY, WALL, HOLE
} OBJ;

typedef enum DIRECTION
{
	UP, DOWN, LEFT, RIGHT
} DIRECTION;

typedef struct CELL
{
	OBJ id;
	struct CELL* up_ptr;
	struct CELL* down_ptr;
	struct CELL* left_ptr;
	struct CELL* right_ptr;
} CELL;

typedef struct DATA
{
	CELL* red_ptr;
	CELL* blue_ptr;
	int try_num;
	DIRECTION tilt_direction;
} DATA;

typedef struct NODE
{
	DATA data;
	struct NODE* next;
} NODE;

typedef struct QUEUE
{
	NODE* head;
	NODE* tail;
} QUEUE;

void queue_init(QUEUE* q)
{
	q->head = NULL;
	q->tail = NULL;
}

void queue_push(QUEUE* q, const DATA data)
{
	NODE* new = (NODE*)malloc(sizeof(NODE));
	new->data = data;
	new->next = NULL;

	if (q->head == NULL) q->head = new;
	else q->tail->next = new;

	q->tail = new;
}

DATA queue_pop(QUEUE* q)
{
	DATA ret;
	NODE* pop_ptr;

	if (q->head == NULL)
	{
		ret.try_num = -1;
		return ret;
	}

	pop_ptr = q->head;
	ret = pop_ptr->data;
	q->head = pop_ptr->next;
	free(pop_ptr);
	return ret;
}

void queue_free(QUEUE* q)
{
	while ((queue_pop(q)).try_num != -1);
}

CELL board[MAX_BOARD_SIZE][MAX_BOARD_SIZE];
DATA move_data;
int N, M;

QUEUE queue;

int move_ball(DATA ball_data, DIRECTION tilt_direction)
{
	CELL* blue_ball_ptr = ball_data.blue_ptr;
	CELL* red_ball_ptr = ball_data.red_ptr;
	CELL* blue_next_ptr = NULL;
	CELL* red_next_ptr = NULL;
	int try_num = ball_data.try_num + 1;
	DATA ball_next;
	int is_blue_change = 1, is_red_change = 1;
	int move_cnt = 0;

	while (is_blue_change | is_red_change)
	{
		is_blue_change = 0; is_red_change = 0;

		switch (tilt_direction)
		{
		case UP:
			blue_next_ptr = blue_ball_ptr != NULL ? blue_ball_ptr->up_ptr : NULL;
			red_next_ptr = red_ball_ptr != NULL ? red_ball_ptr->up_ptr : NULL;
			break;
		case DOWN:
			blue_next_ptr = blue_ball_ptr != NULL ? blue_ball_ptr->down_ptr : NULL;
			red_next_ptr = red_ball_ptr != NULL ? red_ball_ptr->down_ptr : NULL;
			break;
		case LEFT:
			blue_next_ptr = blue_ball_ptr != NULL ? blue_ball_ptr->left_ptr : NULL;
			red_next_ptr = red_ball_ptr != NULL ? red_ball_ptr->left_ptr : NULL;
			break;
		case RIGHT:
			blue_next_ptr = blue_ball_ptr != NULL ? blue_ball_ptr->right_ptr : NULL;
			red_next_ptr = red_ball_ptr != NULL ? red_ball_ptr->right_ptr : NULL;
			break;
		}

		if (blue_next_ptr)
		{
			if (blue_next_ptr->id == HOLE)
			{
				blue_ball_ptr = NULL;
				is_blue_change = 1;
			}
			else if (blue_next_ptr->id != WALL && blue_next_ptr != red_ball_ptr)
			{
				blue_ball_ptr = blue_next_ptr;
				is_blue_change = 1;
				move_cnt++;
			}
		}

		if (red_next_ptr)
		{
			if (red_next_ptr->id == HOLE)
			{
				red_ball_ptr = NULL;
				is_red_change = 1;
			}
			else if (red_next_ptr->id != WALL && red_next_ptr != blue_ball_ptr)
			{
				red_ball_ptr = red_next_ptr;
				is_red_change = 1;
				move_cnt++;
			}
		}
	}

	if (blue_ball_ptr == NULL) return 0;
	else if (red_ball_ptr == NULL) return try_num;
	else if (try_num == MAX_NUM_TRY) return 0;
	else if (move_cnt == 0) return 0;
	else
	{
		ball_next.blue_ptr = blue_ball_ptr;
		ball_next.red_ptr = red_ball_ptr;
		ball_next.try_num = try_num;
		ball_next.tilt_direction = tilt_direction;
		queue_push(&queue, ball_next);
		return 0;
	}
}

int find_best_num()
{
	DATA data_pop;
	int ret;

	while (1)
	{
		data_pop = queue_pop(&queue);
		if (data_pop.try_num == -1) return -1;

		if (data_pop.try_num != 0)
		{
			if (data_pop.tilt_direction == UP || data_pop.tilt_direction == DOWN)
			{
				ret = move_ball(data_pop, LEFT);
				if (ret != 0) return ret;
				ret = move_ball(data_pop, RIGHT);
				if (ret != 0) return ret;
			}
			else
			{
				ret = move_ball(data_pop, UP);
				if (ret != 0) return ret;
				ret = move_ball(data_pop, DOWN);
				if (ret != 0) return ret;
			}
		}
		else
		{
			ret = move_ball(data_pop, UP);
			if (ret != 0) return ret;
			ret = move_ball(data_pop, DOWN);
			if (ret != 0) return ret;
			ret = move_ball(data_pop, LEFT);
			if (ret != 0) return ret;
			ret = move_ball(data_pop, RIGHT);
			if (ret != 0) return ret;
		}
	}
}

int main()
{
	int i, j;
	char str[MAX_BOARD_SIZE + 1];

	move_data.blue_ptr = NULL; move_data.red_ptr = NULL;

	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
	{
		scanf("%s", str);

		for (j = 0; j < M; j++)
		{
			if (str[j] == '.') board[i][j].id = EMPTY;
			else if (str[j] == '#') board[i][j].id = WALL;
			else if (str[j] == 'O') board[i][j].id = HOLE;
			else if (str[j] == 'R')
			{
				board[i][j].id = EMPTY;
				move_data.red_ptr = &board[i][j];
			}
			else if (str[j] == 'B')
			{
				board[i][j].id = EMPTY;
				move_data.blue_ptr = &board[i][j];
			}

			if (i == 0)
			{
				board[i][j].up_ptr = NULL;
				board[i][j].down_ptr = &board[i + 1][j];
			}
			else if (i == N - 1)
			{
				board[i][j].up_ptr = &board[i - 1][j];
				board[i][j].down_ptr = NULL;
			}
			else
			{
				board[i][j].up_ptr = &board[i - 1][j];
				board[i][j].down_ptr = &board[i + 1][j];
			}

			if (j == 0)
			{
				board[i][j].left_ptr = NULL;
				board[i][j].right_ptr = &board[i][j + 1];
			}
			else if (j == M - 1)
			{
				board[i][j].left_ptr = &board[i][j - 1];
				board[i][j].right_ptr = NULL;
			}
			else
			{
				board[i][j].left_ptr = &board[i][j - 1];
				board[i][j].right_ptr = &board[i][j + 1];
			}
		}
	}

	move_data.try_num = 0;
	queue_init(&queue);
	queue_push(&queue, move_data);

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

	queue_free(&queue);

	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다...

qlqh0987 3년 전 0

qlqh0987 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말