(7562) 나이트의 이동

https://www.acmicpc.net/problem/7562

단계별로 풀어보기

27단계(그래프와 순회) 11번째

 

 

 

나이트 이동 방향 같은 경우에도 문자열과 인덱스를 이용한 탐색을 쓰면 쉽게 탐색 코드를 쓸 수 있다(주관적).

 

 

 

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

int solve(){
  int l, sx, sy, ex, ey;
  
  cin >> l >> sx >> sy >> ex >> ey;
  
  vector dist(l, vector<int> (l, -1));
  queue<int> q;
  
  q.push(sx*l+sy);
  dist[sx][sy]= 0;
  
  while(!q.empty()){
    int nowx= q.front()/l;
    int nowy= q.front()%l;
    q.pop();
    
    if(nowx==ex && nowy==ey)  break;
    
    for(int i=0;i<8;i++){
      int nextx= nowx+"34431001"[i]-'2';
      int nexty= nowy+"01344310"[i]-'2';
      
      if(nextx<0 || nextx>l-1 || nexty<0 || nexty>l-1)  continue;
      if(dist[nextx][nexty]!=-1)  continue;
      
      dist[nextx][nexty]= dist[nowx][nowy]+1;
      q.push(nextx*l+nexty);
    }
  }
  
  return dist[ex][ey];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}