본문 바로가기

백준/실버

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

문제링크 : https://www.acmicpc.net/problem/7562

 

#include <bits/stdc++.h> 
using namespace std;

int n, x11, y11, x22, y22, length;  //테스트 케이스, 첫 좌표, 찾을 좌표, 맵의 길이
int arr[300][300];                  //체스 맵 배열
bool check[300][300];               //체스 맵 방문 여부 배열
int dx[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };  // x좌표
int dy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };  // y좌표

void bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x, y });
	check[x][y] = true;
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 8; i++)           //중심 기준 8방향 탐색
		{
			int nx = cur.first + dx[i];       //새로운 x 좌표
			int ny = cur.second + dy[i];      //새로운 y 좌표
			if (nx < 0 || ny < 0 || nx >= length || ny >= length) { continue; } //범위 조건
			if (!check[nx][ny])  
			{
				q.push({ nx, ny });           //새로운 좌표 입력
				check[nx][ny] = true;         //좌표 방문 처리
				arr[nx][ny] = arr[cur.first][cur.second] + 1; //1을 계속 더해줌으로서 카운트 체크
			}
		}
	}
}

int main()
{
	cin >> n;
	while (n--)
	{	
		memset(arr, 0, sizeof(arr));        //arr 배열 초기화 
		memset(check, 0, sizeof(check));    //check 배열 초기화
		cin >> length;
		cin >> x11 >> y11;
		cin >> x22 >> y22;
		bfs(x11, y11);
		cout << arr[x22][y22] << "\n";
	}
	return 0;
}

나이트의 이동 방식에 따라 좌표값(dx, dy)을 수정시켜준다.

'백준 > 실버' 카테고리의 다른 글

[백준 2644번] 촌수계산 (C++)  (0) 2023.02.06
[백준 4963번] 섬의 개수 (C++)  (0) 2023.02.06
[백준 11060번] 점프 점프 (C++)  (0) 2023.02.06
[백준 2193번] 이친수 (C++)  (0) 2023.02.06
[백준 14501번] 퇴사 (C++)  (0) 2023.02.06