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

whdnjqls456 6년 전 0

반례를 못 찾겠습니다 -_-;

행/열 11 일 경우도 된 것 같은데.. 왜 틀리다는 건지;;

3차원 배열로 점프/이동 경우도 다 체크한 것 같은데;;

도움이 절실합니다 ㅠ.!!

#include <stdio.h>
struct point
{
	int x;
	int y;
	int k;
	int t;
};

typedef struct point PT;
PT QUEUE[300001];

int K, low, col;
int map[205][205];
int visit[33][205][205];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int hx[8] = { -1, -2, -2,-1, 1, 2, 2, 1 };
int hy[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };

// 범위 체크 함수
int check(int x, int y)
{
	if (x <= 0 || y <= 0 || x > low || y > col)
		return 0;
	else
		return 1;
}

// 답을 찾는 함수
int BFS()
{
	int front = 0, rear=1;
	int min;

	QUEUE[0].x = 1;
	QUEUE[0].y = 1;
	QUEUE[0].k = 0;
	QUEUE[0].t = 0;

	visit[0][0][0] = 1;

	while (front < rear)
	{
		int nx = QUEUE[front].x;
		int ny = QUEUE[front].y;
		int nk = QUEUE[front].k;
		int nt = QUEUE[front].t;

        // 리턴 조건.
		if (nx == low && ny == col)
			return nt;

		// 그냥 움직일 경우
		for (int i = 0; i < 4; i++)
		{
			int nnx = nx + dx[i];
			int nny = ny + dy[i];

			if (visit[nk][nnx][nny] == 0 && check(nnx, nny)
				&& map[nnx][nny] ==0 )
			{
				visit[nk][nnx][nny] = 1;
				QUEUE[rear].x = nnx;
				QUEUE[rear].y = nny;
				QUEUE[rear].k = nk;
				QUEUE[rear].t = nt+1;
				rear++;
			}
		}

		// 나이트를 움직일 경우
		for (int i = 0; i < 8; i++)
		{
			if (K >= nk)
				break;

			int nnx = nx + hx[i];
			int nny = ny + hy[i];

			if (visit[nk+1][nnx][nny] == 0 && check(nnx, nny)
				&& map[nnx][nny] == 0)
			{
				visit[nk + 1][nnx][nny] = 1;
				QUEUE[rear].x = nnx;
				QUEUE[rear].y = nny;
				QUEUE[rear].k = nk + 1;
				QUEUE[rear].t = nt + 1;
				rear++;
			}
		}
		front++;
	}

	return -1;
}

int main()
{
	int answer;
		
	scanf("%d", &K);
	scanf("%d%d", &col, &low);

	for (int i = 1; i <= low; i++)
		for (int j = 1; j <= col; j++)
			scanf("%d", &map[i][j]);

	answer = BFS();

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

	return 0;
}

djm03178 6년 전 1

if (K >= nk)

방향이 반대 아닐까요?

whdnjqls456 6년 전 0

아 .. 거꾸로 되있었네요.. 감사합니다. (_ _)

djm03178 6년 전 1

지금 런타임 에러 나시는 건, 확실치는 않지만 큐의 크기를 초과하는 경우가 있을 수도 있어서일 것 같네요. 31 * 200 * 200 = 124만이니까요.

whdnjqls456 6년 전 0

정말 현명하십니다!

안그래도 혹시 큐의 크기가 아닌 가 싶어서 늘려봤는데, 역시!!

djm03178님 정말 감사드립니다 (_ _)

밑은 소스이니 혹시 오류나시는 분들은 참고하시면 될 것 같습니다.

#include <stdio.h>
struct point
{
	int x;
	int y;
	int k;
	int t;
};

typedef struct point PT;
PT QUEUE[1500001];

int K, low, col;
int map[205][205];
int visit[33][205][205];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int hx[8] = { -1, -2, -2,-1, 1, 2, 2, 1 };
int hy[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };

// 범위 체크 함수
int check(int x, int y)
{
	if (x <= 0 || y <= 0 || x > low || y > col)
		return 0;
	else
		return 1;
}

// 답을 찾는 함수
int BFS()
{
	int front = 0, rear = 1;
	int min;

	QUEUE[0].x = 1;
	QUEUE[0].y = 1;
	QUEUE[0].k = 0;
	QUEUE[0].t = 0;

	visit[0][1][1] = 1;

	while (front < rear)
	{
		int nx = QUEUE[front].x;
		int ny = QUEUE[front].y;
		int nk = QUEUE[front].k;
		int nt = QUEUE[front].t;

		// 리턴 조건.
		if (nx == low && ny == col)
			return nt;

		// 그냥 움직일 경우
		for (int i = 0; i < 4; i++)
		{
			int nnx = nx + dx[i];
			int nny = ny + dy[i];

			if (visit[nk][nnx][nny] == 0 && check(nnx, nny)
				&& map[nnx][nny] == 0)
			{
				visit[nk][nnx][nny] = 1;
				QUEUE[rear].x = nnx;
				QUEUE[rear].y = nny;
				QUEUE[rear].k = nk;
				QUEUE[rear].t = nt + 1;
				rear++;
			}
		}

		// 나이트를 움직일 경우
		for (int i = 0; i < 8; i++)
		{
			if (K <= nk)
				break;

			int nnx = nx + hx[i];
			int nny = ny + hy[i];

			if (visit[nk + 1][nnx][nny] == 0 && check(nnx, nny)
				&& map[nnx][nny] == 0)
			{
				visit[nk + 1][nnx][nny] = 1;
				QUEUE[rear].x = nnx;
				QUEUE[rear].y = nny;
				QUEUE[rear].k = nk + 1;
				QUEUE[rear].t = nt + 1;
				rear++;
			}
		}
		front++;
	}

	return -1;
}

int main()
{
	int answer;

	scanf("%d", &K);
	scanf("%d%d", &col, &low);

	for (int i = 1; i <= low; i++)
		for (int j = 1; j <= col; j++)
			scanf("%d", &map[i][j]);

	answer = BFS();

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

	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다 ㅠ..

whdnjqls456 6년 전 0

djm03178 6년 전 1

whdnjqls456 6년 전 0

djm03178 6년 전 1

whdnjqls456 6년 전 0

djm03178님 정말 감사드립니다 (_ _)

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말