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

 

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

 

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

7562번: 나이트의 이동

---

 

 

 

해결전략

 

너비우선 탐색, 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;
}

 

 

---