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

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

 

7562번: 나이트의 이동

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	20314	9583	7226	46.490%

 

문제

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

 

 

 

접근 방법 1

시작지점부터 BFS를 돌면서 체스가 이동할 수 있는 8곳을 방문한다. 시작지점부터 해당 지점까지의 거리를 이차원 배열인 fromStart[][]에 저장한다. 1389번과 같은 방식으로 접근했는데 메모리 초과가 떴다. 

 

 

 

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
 
//11부터 시계 반대방향
int dr[8] = {-2,-1,1,2,2,1,-1,-2};
int dc[8] = {-1,-2,-2,-1,1,2,2,1};
 
queue<pair<int,int>> que;
int I, cur1, cur2, next1, next2, cnt;
 
int fromStart[300][300];
 
void settingMap(){
    for(int i = 0; i<I; i++){
        for(int j = 0; j<I; j++){  fromStart[i][j] = 0;}
    }
}
 
 
void printMap(){
    
    for(int i = 0; i<I; i++){
        for(int j = 0; j<I; j++){
            cout << fromStart[i][j] << " ";
            
        } cout << endl;
    }
    cout << endl;
}
 
 
 
int BFS(){
    int res = 0;
    
    while(!que.empty()){
        
        
       // printMap();
        
        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        if(r==next1 && c==next2){           //도착지점이면 그 지점까지의 거리 리턴
            return fromStart[r][c];
        }
 
        for(int i = 0; i<8; i++){
                
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr>=I || nr<0 || nc>=I || nc<0){     //범위 벗어나면 패스
                continue;
            }
           //옮길 곳이 범위 안에 들어옴
 
            que.push(make_pair(nr, nc));
            
            //1. 다음 방문할 곳이 0이면 -> 방문 안한 곳이니까 +1
            if(fromStart[nr][nc]==0){
                fromStart[nr][nc] = fromStart[r][c] + 1;
            }
            //2. 다음 방문할 곳이 0이 아니면 -> 기존 값이랑 비교해서 더 작은것으로 적음
            else{
                
                if(fromStart[nr][nc] > fromStart[r][c] + 1){
                   fromStart[nr][nc] = fromStart[r][c] + 1;
                }
            }
        }
    }
    return -1;
}
 
 
int main(){
    
    int TC;
    cin >> TC;
    for(int t = 0; t<TC; t++){
        
        settingMap();
        cin >> I >> cur1 >> cur2 >> next1 >> next2;
        
        que.push(make_pair(cur1,cur2));
        cout  << BFS() << endl;
        que = queue<pair<int,int>>();
    }
    
    return 0;
}

 

 

 매 테스트 케이스마다 [que = queue<pair<int,int>>();] 로 큐를 초기화했는데도 메모리 초과 문제가 해결되지 않았다.

 

 

 

접근 방법 2

위에서는 말을 이동할 때

기존의 방문할 칸까지의 거리(fromStart[nr][nc]) 가 현재 칸(fromStart[r][c])까지의 거리 +1 보다 클때 더 작은 값으로 교체해주었다. 그러나 그럴 필요가 없었다. 어짜피 BFS로 돌리니까 해당 칸을 방문한 즉시 그 칸까지의 거리가 최소가 되기 때문이다.

 

이번에는fromStart[][]도 매 테스트 케이스마다 초기화하는 코드도 추가했다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
 
//11부터 시계 반대방향
int dr[8] = {-2,-1,1,2,2,1,-1,-2};
int dc[8] = {-1,-2,-2,-1,1,2,2,1};
 
queue<pair<int,int>> que;
int I, cur1, cur2, next1, next2, cnt;
 
int fromStart[300][300];
 
void settingMap(){
    for(int i = 0; i<I; i++){
        for(int j = 0; j<I; j++){  fromStart[i][j] = 0;}
    }
}
 
 
int BFS(){
    int res = 0;
    
    while(!que.empty()){
    
        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        if(r==next1 && c==next2){           //도착지점이면 그 지점까지의 거리 리턴
            res = fromStart[r][c];
            break;
        }
 
        for(int i = 0; i<8; i++){
                
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr>=I || nr<0 || nc>=I || nc<0){     //범위 벗어나면 패스
                continue;
            }
            if(fromStart[nr][nc]==0){               //옮길 곳이 범위 안에 들어오고 방문 안한 곳이면
                fromStart[nr][nc] = fromStart[r][c] + 1;
                que.push(make_pair(nr, nc));
            
            }
        }
   
    }
    return res;
}
 
 
int main(){
    
    int TC;
    cin >> TC;
    for(int t = 0; t<TC; t++){
        
        settingMap();
        cin >> I >> cur1 >> cur2 >> next1 >> next2;
        
        que.push(make_pair(cur1,cur2));
        cout  << BFS() << endl;
        que = queue<pair<int,int>>();
    }
    
    return 0;
}