BOJ 7562: 나이트의 이동

✔ 문제 링크

BOJ 7562: 나이트의 이동

✔ 문제해결전략

• 그래프 탐색
• BFS(Breadth First Search)

✔ 해결과정

• 정직하게 BFS 하면 된다. 보통 2차원에서의 BFS는 상하좌우로 탐색을 하는데 이 문제는 8방향으로 탐색하면 된다.

✔ 정답 Code

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

int main(void) {
	int map[300][300];
	int dx[8] = {1,2,2,1,-1,-2,-2,-1};
	int dy[8] = {2,1,-1,-2,-2,-1,1,2};
	
 	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, l, startX, startY, endX, endY;
	cin >> n;
	queue<pair<int,int>> q;
	
	while(n--) {
		cin >> l;
		cin >> startX >> startY;
		cin >> endX >> endY;
		
		fill(&map[0][0], &map[299][300],-1);
		
  		map[startY][startX] = 0;
		pair<int,int> st = {startY, startX};
  		q.push(st);
  		while(!q.empty()) {
			pair<int,int> cur = q.front();
			q.pop();
			for(int i=0;i<8;i++) {
				int newY = cur.first + dy[i];
				int newX = cur.second + dx[i];
	  			if(newX<0 || newY<0 || newX>=l || newY>=l) continue;
	 	 		if(map[newY][newX] != -1) continue;
	  			map[newY][newX] = map[cur.first][cur.second] + 1;
	  			q.push({newY, newX});
			}
  		}
		cout << map[endY][endX] << '\n';
  	}
}

✔ Check Point

PS 할 때는 보통 전역배열 잡고 하는데 여기서는 fill 함수 사용하기 위해 local로 넣었다. 2차원 배열을 fill 함수로 초기화하려면 시작은 [0, 0], 끝의 row는 MAX-1, coloum은 MAX로 두면 된다. 코드 리팩토링은 다음 기회에..