[백준] 7562번: 나이트의 이동 (C++)

 

그래프 탐색은 너무 가혹합니다..

어제는 DFS를 통해서 문제를 풀었다면

오늘 문제는 BFS를 사용하여 푸는 문제다

 

BFS는 큐를 사용해야 하기 때문에 

나이트의 이동이 저장된 배열, 방문 여부 배열, 방문할 큐, 방문 가능한 방향을 가진 배열

총 4가지 구조체를 사용하여 문제를 풀어야 한다

 

나이트의 이동이 저장된 배열에는

나이트가 가능한 방향 만큼 한 번씩 이동하고

이동한 자리에는 이동한 횟수가 저장된다

과정을 반복하여 목표 자리에 도착했을 때

도착할 때까지 이동한 횟수를 출력한다

 

큐에는 방문할 좌표가 저장되어 있으며

저장한 후에는 pop을 통해 빼는 방식이다

 

 

// baekjoon 7562

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int arr[301][301];
bool visited[301][301] ;

int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};

int L, start_x, start_y, arrive_x, arrive_y;
queue<pair<int, int>> q;


// BFS
void bfs(int cur_x, int cur_y){
    q.push({cur_x, cur_y});
    visited[cur_x][cur_y] = true;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == arrive_x && y == arrive_y){
            cout << arr[x][y] << '\n';
            while (!q.empty()) {
                q.pop();
            }
            break;
        }
        
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if((0 <= nx && 0 <= ny) && (nx < L && ny < L) && !visited[nx][ny]){
                q.push({nx, ny});
                visited[nx][ny] = true;
                arr[nx][ny] = arr[x][y] + 1;
            }
        }
    }
    
}


// 배열, 방문여부, 큐 초기화
void reset(){
    while (!q.empty()) {
        q.pop();
    }
    for(int i = 0; i < 301; i++){
        for(int j = 0; j < 301; j++){
            arr[i][j] = 0;
            visited[i][j] = false;
        }
    }
    
}


int main(){
    init();
    
    int T;
    cin >> T;
    
    for(int i = 0; i < T; i++){
        cin >> L;
        cin >> start_x >> start_y;
        cin >> arrive_x >> arrive_y;
        
        bfs(start_x, start_y);
        reset();
    }
    
}

 

그래프 문제는 변수 하나하나 설정 하는 과정도 쉽지 않고

별도 함수와 전역 변수를 사용하기 때문에

int main() 함수 내에서만 풀던 문제보다 조금 더 어렵게 느껴진다

 

참고 사이트

[백준(BOJ)] 7562번 : 나이트의 이동 - C++[CPP] (tistory.com)

 

아직은 익숙치 않아서

고수님들의 코드를 참고한 후

분석하는 위주로 올려보려고 한다

 

앞으로 실버 한 문제, 골드 네 문제를 더 풀어야 하는데..

노력해보자고