[BOJ] 7562번 : 나이트의 이동

1. problem :

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

 

 

2. solution 1 : 

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

#define X first
#define Y second 
int dx[8] = { 2,2,-2,-2,1,1,-1,-1 };
int dy[8] = { 1,-1,1,-1,2,-2,2,-2 }; 
int T; // testcase 값; 
int row, col;
int dist[302][302];
pair<int, int> initpos;
pair<int, int> finalpos;
queue<pair<int, int>> Q;

int main(void) {
	cin >> T;
	while (T--) {
		int is_arrive = false; 
		cin >> row; 
		col = row; 
		cin >> initpos.X >> initpos.Y;
		cin >> finalpos.X >> finalpos.Y;

		for (int i = 0; i < row; i++) fill(dist[i], dist[i] + col, -1);
		while (!Q.empty()) Q.pop();
		Q.push({ initpos.X,initpos.Y }); 
		dist[initpos.X][initpos.Y] = 0;

		while (!Q.empty()) {
			pair<int, int> cur = Q.front(); Q.pop(); 
			if (cur.X == finalpos.X && cur.Y == finalpos.Y) {
				cout << dist[cur.X][cur.Y] << '\n';
				break;
			}
			for (int dir = 0; dir < 8; dir++) {
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
				if (dist[nx][ny] >= 0) continue;
				dist[nx][ny] = 1 + dist[cur.X][cur.Y]; 
				Q.push({ nx,ny });
			}
		}
	}
	return 0;
}

bfs를 하다가, 목표지점에 도달하면 값을 출력하고 끝낸다. initpos pair <int, int>를 이용하여 정의했다. finalpos도 마찬가지. 

 

3. solution 2 :

// Authored by : yongjunleeme
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/f5754d2b4a6b48ab88efc3e9dcbb1943
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
int dist[305][305];
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int t, n, x, y, xx, yy;
queue <pair<int, int >> Q;

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

  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; i++) fill(dist[i], dist[i] + n, -1);
    cin >> x >> y;
    dist[x][y] = 0;
    Q.push({x, y});
    cin >> xx >> yy;
    while (!Q.empty()) {
      auto cur = Q.front(); Q.pop();
      for (int dir = 0; dir < 8; dir++) {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (dist[nx][ny] >= 0) continue;
        dist[nx][ny] = dist[cur.X][cur.Y] + 1;        
        Q.push({nx, ny});
      }
    }
    cout << dist[xx][yy] << "\n";
  }
}

< source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/7562.cpp >

basic-algo-lecture/0x09/solutions/7562.cpp at master · encrypted-def/basic-algo-lecture

 

bfs를 다 시행한 후 목표지점의 값을 출력한다.