[백준 7562 c++ V] 나이트의 이동

문제 링크

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제 접근

// 문제: 나이트가 한 지점으로부터 목표지점까지 이동하는데 최소이동횟수 구하기
// 접근: 최소이동횟수 -> dfs 시간초과남
// 접근2: bfs로 방문하는 배열에 이동 횟수 저장하면서 이동

 

 

 

문제 풀이

// 풀이: 처음 시작하는 점에서
// 기본 bfs 하는데 이동시 이동 횟수를 저장하면서
// 8방향의 움직임을 반복문으로 구현

 

 

주의

 

 

 

 

 

 

개념

// 개념: memset(visited, 채우는 값, sizeof(visited)); 배열을 초기화 시킴

 

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 7562 c++ V] 나이트의 이동
// 문제: 나이트가 한 지점으로부터 목표지점까지 이동하는데 최소이동횟수 구하기
// 접근: 최소이동횟수 -> dfs 시간초과남
// 접근2: bfs로 방문하는 배열에 이동 횟수 저장하면서 이동
// 풀이: 처음 시작하는 점에서
// 기본 bfs 하는데 이동시 이동 횟수를 저장하면서
// 8방향의 움직임을 반복문으로 구현
// 개념: memset(visited, 채우는 값, sizeof(visited)); 배열을 초기화 시킴

using namespace std; // cin,cout 편하게 사용 라이브러리
#define MAX 301

int t;
int n;
int krow, kcol;
int tarrow, tarcol;
// 나이트 이동 8 방향 
int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { -1,1,-2,2,-2,2,-1,1 };
int visited[MAX][MAX];


void bfs(int row, int col)
{
	// 시작 점 방문표시
	queue<pair<int, int>> q;
	q.push({ row,col });
	visited[row][col] = 0;

	while (!q.empty())
	{
		int currow = q.front().first;
		int curcol = q.front().second;
		q.pop();
		// 목표지점이면 이동횟수 출력
		if (currow == tarrow && curcol == tarcol)
		{
			cout << visited[tarrow][tarcol] << '\n';
			return;
		}
		// 8방면 이동
		for (int i = 0; i < 8; i++)
		{
			int nrow = currow + dy[i];
			int ncol = curcol + dx[i];
			// 범위 안에 있고 방문 않했으면
			if (nrow >= 0 && ncol >= 0 && nrow < n && ncol < n)
			{
				if (visited[nrow][ncol] == 0)
				{
					// 배열 자체에 이동거리 입력
					visited[nrow][ncol] = visited[currow][curcol]+1;
					q.push({ nrow,ncol });
					
				}
			}
		}
		
	}
}


int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); // 입출력 시간 단축
	cout.tie(NULL);
	// 입력
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n;
		cin >> krow >> kcol;
		cin >> tarrow >> tarcol;
		bfs(krow, kcol);
		// 방문배열 초기화
		memset(visited, 0, sizeof(visited));
	}
	
	return 0;
}