-
[백준 7562] 나이트의 이동C 프로그래밍/BOJ 2022. 9. 5. 20:25728x90
https://www.acmicpc.net/problem/7562
#include <cstdio> #include <iostream> #include <queue> int T; // 테케 수 int N; // 체스판 한 변의 길이 int cx, cy, fx, fy; // (cx, cy) : 현재 위치 (fx, fy) : 미래 위치 bool visited[300 + 10][300 + 10]; // 체스판 한 변의 최대 길이 : 300 struct _st { int x; int y; int move; }; std::queue<_st> Q; void init(void) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { visited[i][j] = false; } } } int game(void) { int dir_x[8] = { -2, -1, 1, 2, 2, 1, -1, -2 }; int dir_y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; if (cx == fx && cy == fy) return 0; Q = {}; // 테케 여러개이므로 큐 초기화 필요 Q.push({ cx, cy, 0 }); visited[cx][cy] = true; while (!Q.empty()) { _st data = Q.front(); Q.pop(); for (int p = 0; p < 8; p++) { int nx = data.x + dir_x[p]; int ny = data.y + dir_y[p]; int nmove = data.move + 1; if (nx == fx && ny == fy) return nmove; if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1 || visited[nx][ny] == true) continue; Q.push({ nx, ny, nmove }); visited[nx][ny] = true; } } } int main() { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d", &N); scanf("%d %d %d %d", &cx, &cy, &fx, &fy); int ans = game(); printf("%d\n", ans); init(); } return 0; }
이 문제도 전형적인 BFS 문제로, 나이트가 최소 몇 번만에 이동할 수 있는지 묻고있다.
// init( ) 함수
아래 미로탐색 문제와 거의 100% 로직이 동일하다.
다만 테스트케이스를 여러 개 입력받으므로, 큐와 방문배열을 초기화해주는 것이 필요하다.
// game( ) 함수
나이트가 한 번에 이동할 수 있는 위치의 종류가 8가지임을 고려해야 한다.
만약 현재 위치와 가려는 위치가 같다면 움직이지 않아도 되기 때문에 0을 리턴해주었다.
728x90'C 프로그래밍 > BOJ' 카테고리의 다른 글
[백준 1398] 케빈 베이컨의 6단계 법칙 (0) 2022.09.06 [백준 1963] 소수 경로 (0) 2022.09.05 [백준 2178] 미로 탐색 (0) 2022.09.05 [백준 3190] 뱀 (0) 2022.09.04 [백준 10655] 마라톤1 (0) 2022.09.02