[백준 BOJ7562] 나이트의 이동 (C++)

1. 제목

- 백준 7562 나이트의 이동

- BOJ 7562 나이트의 이동

문제 링크 :7562번: 나이트의 이동 (acmicpc.net)

7562번: 나이트의 이동

---

2. 문제 설명

나이트의 이동

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	41465	20902	15643	49.402%

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2001 3번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: sait2000
• 문제의 오타를 찾은 사람: sgchoi5

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

5
28
0

---

3. 풀이 과정

시작 지점 좌표를 큐에 넣어 놓은 다음 갈 수 있는 모든 지역을 탐색하면서 풀어 봤어요. visit 배열은 따로 사용하지 않았고 대신 각 맵은 시작 지점부터 해당 지점까지 가는 데 걸리는 시간을 저장하는 식으로 -1 라면 도착 지점, 0이라면 아직 방문하지 않은 지역, 1 이상이라면 방문했던 지역이며 이 값은 출발지부터 해당 지점까지 방문하는데 걸리는 시간을 표현 하는 거죠. 그래서 따로 방문처리를 표시할 visit 배열이 필요 없었어요.

 

맵을 처음 구성 할 때 도착지점을 -1 , 시작지점은 1로 표시해두고 

탐색 구역이 -1라면 도착지점을 찾은 것 이므로 처음 시작 지점을 표시하느라 1로 표현 해서 걸리는 시간이 +1 되있으니 지금 지역 도착시간을 바로 넣으면 정답 값이 나오게 돼요

---

4. 함수 설명

Reset() : 테스트 케이스가 끝날때마다 맵과 큐를 초기상태로 초기화 해주는 작업이 필요해요.

그래서 BFS탐색이 한번 끝날때 마다 맵사이즈만큼 다시 0으로 초기화 해주고 큐에 들은것도 다 제거 해주는 함수에요.

 

 

---

5. 코드

#define MAX 300 + 1
#define Y first
#define X second
#include <iostream>
#include <queue>

using namespace std;


// 나이트의 탐색 방향 일반적인 상하좌우가 아니에요.
// https://www.acmicpc.net/problem/7562
// 총 8방향이동 하니까 배열도 8개 만들어주기
// 좌상단부터 우상단순으로 넣었어요
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int map[MAX][MAX];
// I : 체스판의 크기는 I*I 이에요
int I;
queue<pair<int, int>> q;

// 테스트 케이스가 끝날때마다 맵과 큐를 초기상태로 초기화 해주는 작업이 필요해요.
void reset()
{
	for (int y = 0; y < I; y++)
	{
		for (int x = 0; x < I; x++)
		{
			map[y][x] = 0;
		}
	}

	while (!q.empty())
		q.pop();
}

void Bfs(int y, int x)
{
	// 시작지점 큐에 넣어놓고
	q.push({y, x});
	// 큐가 빌때까지 BFS 탐색 하기
	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();		

		for (int dir = 0; dir < 8; dir++)
		{
			// 8방향 탐색
			int ny = cur.Y + dy[dir];
			int nx = cur.X + dx[dir];

			// 탐색 지점이 맵을 벗어났다면 스킵
			if (ny < 0 || nx < 0 || ny >= I || nx >= I)
				continue;
			// 도착 지점을 찾았다면 현재 맵에 있는 시간을 도착지점에 넣어놓고 탐색을 끝낸다.
			if (map[ny][nx] == -1)
			{
				map[ny][nx] = map[cur.Y][cur.X];
				return;
			}
			// 이미 방문한 지점이라면 스킵한다
			if (map[ny][nx] != 0)
				continue;

			// 맵에는 각지점에 도달하기 까지 걸리는 시간이 들어있는것을 구현하기위해 1씩 더해줌
			map[ny][nx] = map[cur.Y][cur.X] + 1;
			q.push({ny, nx});
				
		}
	}
}

int main()
{
	// t : 테스트케이스 개수
	int t;
	cin >> t;

	// 테스트케이스 개수만큼 실행
	for (int i = 0; i < t; i++)
	{
		// 체스판 크기 설정해주기
		cin >> I;

		// 나이트 시작 지점
		int startY, startX;
		cin >> startY >> startX;
		// 나이트 도착 지점
		int endY, endX;
		cin >> endY >> endX;

		// 시작 지점은 1부터 시작
		map[startY][startX] = 1;
		// 도착 지점은 -1로 표시해두기
		map[endY][endX] = -1;

		// 시작 지점부터 BFS 탐색 시작하기
		Bfs(startY, startX);
		cout << map[endY][endX] << "\n";
		reset();
	}

	return 0;
}