[C] 백준 - 7562번: 나이트의 이동

6월 7일(수) - 그래프와 순회 (7562번)

7562번: 나이트의 이동

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

typedef struct {
	int x;
	int y;
}point;

int length, start_x, start_y, end_x, end_y;
int board[301][301] = { 0, };
int visit[301][301] = { 0, };
int front = -1;
int rear = -1;

int move[8][2] = { {-2,1},{-2,-1},{2,1},{2,-1},{1,-2},{-1,-2},{1,2},{-1,2} };
int d[301 * 301];
point q[301 * 301];

int bfs(int y, int x)
{
	memset(visit, 0, sizeof(visit));
	memset(q, 0, sizeof(q));
	memset(d, 0, sizeof(d));

	q[rear].x = x;
	q[++rear].y = y;
	visit[y][x] = 1;

	while (front < rear)
	{
		int xx = q[front].x;
		int yy = q[++front].y;

		for (int i = 0; i < 8; i++)
		{
			int xxx = xx + move[i][1];
			int yyy = yy + move[i][0];

			if (xxx < 0 || yyy < 0 || xxx >= length || yyy >= length)
			{
				continue;
			}
			if (xxx == end_x && yyy == end_y && visit[yyy][xxx] == 0)
			{
				return d[front] + 1;
			}
			else if (visit[yyy][xxx] == 0)
			{
				q[rear].x = xxx;
				q[++rear].y = yyy;
				visit[yyy][xxx] = 1;
				d[rear] = d[front] + 1;
			}
		}
	}
	
	return 0;
}

int main(void)
{
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++)
	{
		memset(board, 0, sizeof(board));
		scanf("%d", &length);
		scanf("%d %d", &start_x, &start_y);
		scanf("%d %d", &end_x, &end_y);

		printf("%d\n", bfs(start_y, start_x));

	}

	return 0;
}

1. 런타임 에러 (OutOfBounds) 가 발생

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(참고 -> https://iamthejiheee.tistory.com/22 )

( 런타임 에러 발생 이유 모르겠음 )

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include<stdio.h>
#include<string.h>
#define SZ 301
#define QUE_SZ 90001

int chess_board[SZ][SZ] = { 0 };
int test_case, chess_size;

int vectY[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int vectX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };

struct node {
	int x;
	int y;
};
struct node queue[QUE_SZ];
int tail = 0;
int head = 0;

void enque(int a, int b)
{
	struct node temp;
	temp.x = a; temp.y = b;
	queue[tail] = temp;
	tail = (tail + 1) % QUE_SZ;
}

struct node deque(void)
{
	struct node temp = queue[head];
	head = (head + 1) % QUE_SZ;
	return temp;
}

int isQueEmpty(void)
{
	return (head == tail) ? 1 : 0;
}

void do_bfs(void)
{
	struct node temp;
	while (isQueEmpty() == 0)
	{
		temp = deque();
		int a = temp.x; int b = temp.y;

		int nextX; int nextY;
		for (int i = 0; i < 8; i++)
		{
			nextX = a + vectX[i];
			nextY = b + vectY[i];

			if (nextX >= 0 && nextY >= 0 && nextX < chess_size && nextY < chess_size) {
				if (chess_board[nextX][nextY] == 0) {
					chess_board[nextX][nextY] = chess_board[a][b] + 1;
					enque(nextX, nextY);
				}
			}
		}
	}
	return;
}

void solution(int chess_start_x, int chess_start_y, int chess_dst_x, int chess_dst_y)
{
	chess_board[chess_start_x][chess_start_y] = 1;
	enque(chess_start_x, chess_start_y);
	do_bfs();
	printf("%d\n", chess_board[chess_dst_x][chess_dst_y] - 1);
	return;
}

int main(void)
{
	scanf("%d", &test_case);
	int chess_start_x, chess_start_y, chess_dst_x, chess_dst_y;

	for (int i = 0; i < test_case; i++)
	{
		scanf("%d", &chess_size);
		scanf("%d %d", &chess_start_x, &chess_start_y);
		scanf("%d %d", &chess_dst_x, &chess_dst_y);

		memset(chess_board, 0, sizeof(chess_board));
		solution(chess_start_x, chess_start_y, chess_dst_x, chess_dst_y);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ