JArchive 프로그래밍 일기

문제

나이트의 이동 백준 7562

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int tc, n, curx, cury, targetx, targety;
int board[303][303];
bool vis[303][303] = {false};
int dx[] = {2, 1, 2, 1, -2, -1, -2, -1}; // 현재칸 기준 8방향으로 이동 가능 
int dy[] = {1, 2, -1, -2, 1, 2, -1, -2};

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < n);
}

void init(){
  for(int i = 0; i <302; i++) fill(board[i], board[i]+302, 0);
  for(int i = 0; i <302; i++) fill(vis[i], vis[i]+302, false);
}

int bfs(int ci, int cj, int ti, int tj){

  queue<pair<pair<int,int>, int>> qu; //  {좌표, 이동 횟수}

  vis[ci][cj] = true;
  qu.push({{ci, cj}, 0});

  while(!qu.empty()){
    int curx = qu.front().X.X;
    int cury = qu.front().X.Y;
    int curcnt = qu.front().Y;
    qu.pop();

    if(curx == ti && cury == tj){ // 목적지 좌표 도착 
      return curcnt;
    }

    for(int i = 0; i < 8; i++){
      int nx = curx + dx[i];
      int ny = cury + dy[i];

      if(!checkrange(nx, ny) || vis[nx][ny]) continue;
      vis[nx][ny] = true;
      qu.push({{nx,ny}, curcnt + 1});
    }

  }
  return 0;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> tc;

  while(tc--){
    init(); // 체스판과 방문배열 초기화
    cin >> n; // 체스판 한 변의 길이
    cin >> curx >>  cury >> targetx >> targety; // 현재칸, 목적지 칸
    int cnt = bfs(curx, cury, targetx, targety);
    cout << cnt << '\n';
  }

  return 0;
}

리뷰

기본적인 bfs 문제였다.
상하좌우 4칸이 아니라, 나이트가 갈 수 있는 (1, 2) 만큼 차이나는 8칸을 모두 확인해야 한다.

bfs 큐는 좌표와 이동횟수를 함께 넣어준다.
유효범위 인지 확인하고, 방문하지 않았는지 확인한 다음 큐에 넣어준다.