JXNVCE ALGO-LOG YouJin Jung

BOJ-7562

29 Jul 2021

BFS 를 활용한 문제!!! 아직도 헷갈리니까 연습 많이 하자….✨✨ 이런 방향성이 있는 문제에 대한 접근 방법을 몰라서, 구글링해서 참고를 했다. x축 방향, y축 방향을 나누어 array로 dx dy 이렇게 담아 하는 새로운 테크닉도 배웠다. 참 신기한 알고리즘의 세계….😎

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int arr[301][301];
bool checked[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 dx[8] = {1,2,2,1,-1,-2,-2,-1};
// int dy[8] = {2,1,-1,-2,-2,-1,1,2};
 
int I;
queue<pair<int, int>> q;
int xs, ys, xd, yd;
 
void bfs(int a, int b){
    q.push(make_pair(a, b));
    checked[a][b] = true;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if(x == dstX && y == dstY){
            cout << arr[x][y] << endl;
            while(!q.empty()) q.pop();
        }
        
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < I && ny >= 0 && ny < I){
                if(checked[nx][ny] == false){
                    checked[nx][ny] = true;
                    arr[nx][ny] = arr[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
    
    int T;
    cin >> T;
 
    for(int i = 0; i < T; i++){
        cin >> I;
        if (I<4 || I>300) return 0;
        cin >> xs >> ys >> xd >> yd;
        bfs(xs, ys);
        memset(arr, 0, sizeof(arr));
        memset(checked, false, sizeof(checked));
    }
    return 0;
}

Related posts