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

 

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

 

https://www.acmicpc.net/problem/7562

 

7562번: 나이트의 이동

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

www.acmicpc.net

---

 

 

 

해결전략

 

너비우선 탐색, BFS

 

---

 

 

코드

 

#include <iostream>
#include <queue> 
#include <vector>
#include <cstring> // 메모리를 설정하는 함수들을 사용하기 위한 라이브러리 (예: memset)
using namespace std;
 
int t, n; // t: 테스트 케이스의 수, n: 체스판 한 변의 길이
int c, d; // 도착 위치 (c,d)
 
int ch[301][301]; // 각 위치에 대해 방문 여부 및 이동 횟수를 저장하는 배열 
queue<pair<int,int>> Q;  // BFS에서 사용할 큐. 각 pair는 (y,x) 좌표를 나타냅니다.
 
// 나이트가 움직일 수 있는 8가지 방향을 정의한 배열
int dirY[8] = { -1, -2, -1, -2, 1, 2, 1, 2 };
int dirX[8] = { -2,-1 ,2 ,1 ,-2,-1 ,2 ,1 };
 
// BFS 함수 정의. 시작점 (a,b)를 인자로 받습니다.
void BFS(int a,int b)
{
	memset(ch,-1,sizeof(ch));	// 모든 위치에 대해 방문 여부 및 이동 횟수 초기화
	
	Q.push(make_pair(a,b));	// 시작점을 큐에 넣음
	ch[a][b] = 0;			// 시작점에서의 이동 횟수는 0
 
	while(!Q.empty())		// 큐가 비어있지 않은 동안 반복
	{
		int y=Q.front().first;
		int x=Q.front().second;
		Q.pop();			 
 
		if(y==c && x==d){		               // 현재 위치가 도착점과 같으면,
			cout << ch[c][d] << "\n";  		   // 해당 위치까지의 최소 이동 횟수 출력하고 함수 종료.
			return;
		}
		
        for(int i=0;i<8;i++)				         	  // 모든 가능한 방향에 대해,
        {
            int ny=y+dirY[i];
            int nx=x+dirX[i];
			
            if(0<=ny && ny<n && 0<=nx && nx<n && ch[ny][nx]==-1)  		 	 	 	  			 			 			          	 	   	   	  		 			   	 		          			  	      	    	   	  	 	             		  		 				 				  			 	    		  	   		   	  	 			  		 	  		   	  	 				  		 				 				 		 	  	 		 	  			 	 		          			  	      	    	   	  	 	             		  		 				 				  			 	    		  	   		   	  	 			  		 	  		   	  	 				  		 				 				 		 	  	 		 	  				// 아직 방문하지 않았고, 체스판 범위 내에 있는 경우
            {
                Q.push(make_pair(ny,nx)); // 그 위치를 큐에 넣고,
                ch[ny][nx]=ch[y][x]+1; // 시작점에서 해당 위치까지의 이동 횟수를 저장.
            }
        }		
    }
 
    return;
}
 
int main(){
    ios::sync_with_stdio(false);	// 입출력 속도 향상을 위한 설정
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> t; 	// 테스트 케이스의 수 입력
 
    while(t--) 	// 각 테스트 케이스에 대해,
    {
        cin >> n; 	// 체스판 한 변의 길이 입력
 
        int a, b;
        cin >> a >> b;  // 시작점 (a,b) 입력
        cin >> c >> d;  // 도착점 (c,d) 입력
 
        BFS(a, b); 	  // BFS 함수 호출
 
        while(!Q.empty())		       
        {
            Q.pop();	// 다음 테스트 케이스를 위해 큐 초기화
        }
    }
 
    return 0;
}

 

 

---