글 읽기 - 약간 dfs 적으로 접근해서 풀어봤는데 반례를 찾이 못하겠습니다. 도와주세요 :(

shfshfdl 4년 전 1

안녕하세요 우선 예제와 게시판에 잇는 반례들은 통과하는것은 확인했습니다.

0% 에서 바로 틀렸습니다를 받는데

우선 제 로직은 이렇습니다.

shark 배열에 값이 있으면 해당 상어를 다음지점으로 이동시킵니다.

그때 만약 거기에 상어가 이미 있다면 해당상어를 재귀적으로 다음지점으로 계속 밀어내는 식으로 구현했습니다.

반례가 어떤게 있을까요?

그리고 추가적으로 반례를 어떻게 유추하는지 좋은 디버깅 방법있으시면 공유부탁드리겠습니다. ㅠㅠ

감사합니다.

#include <iostream>
using namespace std;
#define MXRC 100
#define MXSHARK (MXRC*MXRC)
#define UP 1
#define DN 2
#define RT 3
#define LT 4
int R, C, M;

int dy[] = { 0, -1, 1, 0, 0 };
int dx[] = { 0, 0, 0, 1, -1 };

struct SHARK {
	int speed, direction, size;
	SHARK() {
		this->speed = -1; this->direction = -1; this->size = -1;
	}
	SHARK(int speed, int direction, int size) {
		this->speed = speed; this->direction = direction; this->size = size;
	}
};
SHARK shark[MXRC + 3][MXRC + 3];
bool visit[MXRC + 3][MXRC + 3] = { 0, };

int fishing(int x);

void move(int from_y, int from_x) {
	int speed = shark[from_y][from_x].speed;
	int direction = shark[from_y][from_x].direction;
	int size = shark[from_y][from_x].size;
	int ny = from_y, nx = from_x;

	if (visit[from_y][from_x] == false) {
		visit[from_y][from_x] = true;
		shark[from_y][from_x] = SHARK();
	}

	if (direction == 1 || direction == 2)
	{
		int Rotate = (R - 1) * 2;
		if (speed >= Rotate) speed = speed % Rotate;

		for (int j = 0; j < speed; j++)
		{
			nx = from_x + dx[direction];
			ny = from_y + dy[direction];
			if (ny < 1)
			{
				direction = 2;
				ny = ny + 2;
			}
			if (ny > R)
			{
				direction = 1;
				ny = ny - 2;
			}
			from_x = nx;
			from_y = ny;
		}
	}
	else
	{
		int Rotate = (C - 1) * 2;
		if (speed >= Rotate) speed = speed % Rotate;

		for (int j = 0; j < speed; j++)
		{
			nx = from_x + dx[direction];
			ny = from_y + dy[direction];
			if (nx < 1)
			{
				direction = 3;
				nx = nx + 2;
			}
			if (nx > C)
			{
				direction = 4;
				nx = nx - 2;
			}
			from_x = nx;
			from_y = ny;
		}
	}

	if (shark[ny][nx].speed != -1) {
		if (visit[ny][nx] == false) {
			move(ny, nx);
			shark[ny][nx].direction = direction;
			shark[ny][nx].size = size;
			shark[ny][nx].speed = speed;
			visit[ny][nx] = true;
		}
		else {
			if (shark[ny][nx].size < size) {
				shark[ny][nx].direction = direction;
				shark[ny][nx].size = size;
				shark[ny][nx].speed = speed;
				visit[ny][nx] = true;
			}
		}
	} else {
		shark[ny][nx].direction = direction;
		shark[ny][nx].size = size;
		shark[ny][nx].speed = speed;
		visit[ny][nx] = true;
	}
}

void move() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			visit[i][j] = false;
		}
	}
	for (int i = 1; i <= R; i ++ ) {
		for (int j = 1; j <= C; j++) {
			if (shark[i][j].size == -1 || visit[i][j] == true) continue;
			move(i, j);
		}
	}
}

int main() {
	cin >> R >> C >> M;

	int r, c, speed, direction, size;

	for (int i = 0; i < M; i++) {
		cin >> r >> c >> speed >> direction >> size;
		shark[r][c] = SHARK(speed, direction, size);
	}

	int man_x = 1;
	int total = 0;
	while (man_x != C + 1) {
		total += fishing(man_x);
		move();
		man_x++;
	}
	cout << total << endl;

	return 0;
}

int fishing(int x) {
	for (int i = 1; i <= R; i++) {
		if (shark[i][x].speed != -1) {
			int size = shark[i][x].size;
			shark[i][x] = SHARK();
			return size;
		}
	}
	return 0;
}

shfshfdl 4년 전 0

자문자답입니다.

기존에 있던 상어가 이동을 했는데 다시 제자리로 오는 경우가 발생해

size를 체크하고 교체를 해줘야하는 경우가 있엇습니다.

89번째 라인에 size 체크 추가하니 성공했습니다.

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

문제

문제

출처

ICPC

약간 dfs 적으로 접근해서 풀어봤는데 반례를 찾이 못하겠습니다. 도와주세요 :(

shfshfdl 4년 전 1

shfshfdl 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말