[백준/C++] 7562번_나이트의 이동♟

문제는 다음과 같습니다.

너무나도 전형적인 bfs문제이구요,
stl queue 자료구조를 이용하였고,
시작점을 먼저 큐에 넣고 이후에 bfs를 진행하였습니다.

갈 수 있는 방향은 총 8개이고,
갈 수 있는 방향이 해당 범위에 만족하면 이를 큐에 넣어서 계속 진행하도록 하였습니다.

그리고 가장 먼저(최소한의 이동으로) 도착점에 도착한 것이 답이 되므로,
이때 바로 bfs에서 탈출하여 정답을 출력하도록 했습니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int c, l; cin>>c;

    while(c--){
      cin>>l; // 체스판 한한 변의 길이
      
      int ch[302][302]={0, };
      queue<pair<pair<int, int>, int>> q;
      int s1, s2, f1, f2; cin>>s1>>s2>>f1>>f2;
      s1++; s2++; f1++; f2++; // 양변 테두리 맞추기

      int res=0;
      ch[s1][s2]=1;
      q.push({{s1, s2}, res});

      // bfs 수행
      while(!q.empty()){
        pair<pair<int, int>, int> p = q.front(); q.pop();
        int i = p.first.first; int j = p.first.second;
        res = p.second;
        if(i==f1 && j==f2) break;

        if(ch[i-1][j-2]==0 && i-1>=1 && j-2>=1){
          ch[i-1][j-2]=1; q.push({{i-1, j-2}, res+1});
        }
        if(ch[i-2][j-1]==0 && i-2>=1 && j-1>=1){
          ch[i-2][j-1]=1; q.push({{i-2, j-1}, res+1});
        }

        if(ch[i-2][j+1]==0 && i-2>=1 && j+1<=l){
          ch[i-2][j+1]=1; q.push({{i-2, j+1}, res+1});
        }
        if(ch[i-1][j+2]==0 && i-1>=1 && j+2<=l){
          ch[i-1][j+2]=1; q.push({{i-1, j+2}, res+1});
        }

        if(ch[i+1][j+2]==0 && i+1<=l && j+2<=l){
          ch[i+1][j+2]=1; q.push({{i+1, j+2}, res+1});
        }
        if(ch[i+2][j+1]==0 && i+2<=l && j+1<=l){
          ch[i+2][j+1]=1; q.push({{i+2, j+1}, res+1});
        }

        if(ch[i+2][j-1]==0 && i+2<=l && j-1>=1){
          ch[i+2][j-1]=1; q.push({{i+2, j-1}, res+1});
        }
        if(ch[i+1][j-2]==0 && i+1<=l && j-2>=1){
          ch[i+1][j-2]=1; q.push({{i+1, j-2}, res+1});
        }
      } // bfs 끝

      cout<<res<<"\n";
    } // while문 끝

    return 0;
}

2/19 토요일 복습)

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, t, d; cin>>t;
  
  while(t--){
    queue<pair<pair<int, int>, int>> q;
    int a[302][302]={0, }; int ch[302][302]={0, };
    cin>>n;
    int s1, s2; cin>>s1>>s2; // 시작점 입력
    int e1, e2; cin>>e1>>e2; // 도착점 입력

    ch[s1][s2]=1; q.push({{s1, s2}, 0});

    while(!q.empty()){
      pair<pair<int, int>, int> p = q.front(); q.pop();
      int t1 = p.first.first; int t2 = p.first.second; d = p.second;

      if(t1==e1 && t2==e2) break;

      if(t1-2>=0 && t2+1<n && ch[t1-2][t2+1]==0){
        ch[t1-2][t2+1]=1; q.push({{t1-2, t2+1}, d+1});
      }
      if(t1-1>=0 && t2+2<n && ch[t1-1][t2+2]==0){
        ch[t1-1][t2+2]=1; q.push({{t1-1, t2+2}, d+1});
      }
      if(t1+1<n && t2+2<n && ch[t1+1][t2+2]==0){
        ch[t1+1][t2+2]=1; q.push({{t1+1, t2+2}, d+1});
      }
      if(t1+2<n && t2+1<n && ch[t1+2][t2+1]==0){
        ch[t1+2][t2+1]=1; q.push({{t1+2, t2+1}, d+1});
      }
      if(t1+2<n && t2-1>=0 && ch[t1+2][t2-1]==0){
        ch[t1+2][t2-1]=1; q.push({{t1+2, t2-1}, d+1});
      }
      if(t1+1<n && t2-2>=0 && ch[t1+1][t2-2]==0){
        ch[t1+1][t2-2]=1; q.push({{t1+1, t2-2}, d+1});
      }
      if(t1-1>=0 && t2-2>=0 && ch[t1-1][t2-2]==0){
        ch[t1-1][t2-2]=1; q.push({{t1-1, t2-2}, d+1});
      }
      if(t1-2>=0 && t2-1>=0 && ch[t1-2][t2-1]==0){
        ch[t1-2][t2-1]=1; q.push({{t1-2, t2-1}, d+1});
      }
    } // bfs문 끝
    cout<<d<<"\n";

  }
  return 0;
}