JArchive 프로그래밍 일기

문제

나이트의 이동 백준 7562번

리뷰

이동 횟수를 체스판 좌표에 저장하려고 한 방식이 실패했다.

왜냐하면 그 좌표를 지나간 경우가 하나가 아니기 때문이다.

큐에는 이동 좌표를 저장했다. 이동 횟수인 int cnt는 따로 관리했다. 범위 내부이고, 안가본 좌표라면, 체스판 해당 좌표에 cnt를 저장하려고 했다.

int M[M_MAX+1][M_MAX+1]; // 체스판  - 0이 아니면 (미방문시) cnt값을 저장

int cnt = 0; 

queue<pair<int,int>> q;    //좌표를 저장하는 큐 
M[tmpX][tmpY] = cnt;

그래서 큐에 좌표와 cnt를 함께 저장했다.

int M[M_MAX+1][M_MAX+1]; // 체스판   - 방문1 미방문0 만 구분 
int cnt = 0; 

// q : 현재 좌표{a,b}와 이동 횟수cnt 저장  
queue<pair<pair<int,int>,int>> q;    

q.push({{a, b}, cnt} ); // 현재좌표와 이동횟수 0 푸시  
M[a][b] = 1; // 현재좌표 방문표시

범위 내부이고, 안가본 좌표라면, 이동한 좌표 tmpX tmpY 이동횟수+1 을 큐에 푸시했다.

// 8 방향 확인  
for(int i = 0; i < 8; i++){ 

    int tmpX = nx + dx[i]; // 가볼 좌표  
    int tmpY = ny + dy[i];

    if(boundary(tmpX, tmpY)){ // 범위 내부이면 

        if(M[tmpX][tmpY] == 0){ // 안가봤다면 

            q.push({ {tmpX, tmpY}, cnt+1} ); // 큐에 이동한 좌표와 이동횟수+1 해서  푸시 
            M[tmpX][tmpY] = 1; //방문표시   
        }
    }
} 

큐에서 pop 했을 때의 좌표가 목적지 좌표라면, 바로 cnt를 return 하게 했다.

어려웠다. 나중에 다시 풀어봐야겠다.

코드

#include <iostream> 
#include <queue>
#include <cstring> // memset()
#include <algorithm> // min(), pair STL
#define M_MAX 300
using namespace std;


int M[M_MAX+1][M_MAX+1]; // 체스판  
int M_LIMIT; // 체스판 크기 
int a,b, x,y; // 현재좌표, 목적좌표  

// 8방향 
int dx[10] = {1, 2, 2, 1, -2, -1, -2, -1}; 
int dy[10] = {2, 1, -1, -2, 1, 2, -1, -2};


// M_LIMIT 범위 내에 있는지 확인
bool boundary(int i, int j){   
    return (i >= 0 && i < M_LIMIT && j >= 0 && j < M_LIMIT) ? 1:0;
} 

int BFS(){

    int cnt = 0;

    // q : 현재 좌표{a,b}와 이동 횟수cnt 저장  
    queue<pair<pair<int,int>,int>> q;    

    q.push({{a, b}, cnt} ); // 현재좌표와 이동횟수 0 푸시  
    M[a][b] = 1; // 현재좌표 방문표시


    while(!q.empty()){

        pair<pair<int,int>,int> now = q.front();
        q.pop();

        int nx = now.first.first; // 현재 좌표  
        int ny = now.first.second; 
        int cnt = now.second; // 여기까지의 이동횟수 cnt 

        // 목적지라면 종료 
        if(nx == x && ny == y){
            return cnt;
        } 

        // 8 방향 확인  
        for(int i = 0; i < 8; i++){ 

            int tmpX = nx + dx[i]; // 가볼 좌표  
            int tmpY = ny + dy[i];

            if(boundary(tmpX, tmpY)){ // 범위 내부이면 

                if(M[tmpX][tmpY] == 0){ // 안가봤다면 

                    q.push({ {tmpX, tmpY}, cnt+1} ); // 큐에 이동한 좌표와 이동횟수+1 해서  푸시 
                    M[tmpX][tmpY] = 1; //방문표시   
                }
            }
        } 
    }
}

int main(void){

     int TC = 0;
     cin >> TC;

    while(TC--){
        cin >> M_LIMIT; // 체스판 크기(범위)
        cin >> a >> b >> x >> y; // 현재좌표, 목적좌표 
        memset(M, 0, sizeof(M)); // 체스판 0초기화 

         cout << BFS() << '\n';    
     }

    return 0;    
}