Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Archives
Today
Total
관리 메뉴

hwooo

BOJ (C/C++) 7562번: 나이트의 이동 본문

Study/Algorithm

BOJ (C/C++) 7562번: 나이트의 이동

hwooo 2022. 12. 4. 01:21

풀이

BFS 사용해서 최소 이동 횟수를 찾음


코드

#include <stdio.h>
#include <queue>
using namespace std;

int l;
int Moving(int sx, int sy, int ex, int ey) {
	// 출발 지점 = 도착 지점
	if (sx == ex && sy == ey) return 0;

	int move[8][2] = { {-1,-2}, {-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };
	int x, y, nx, ny, cnt;
	int visited[300][300] = { 0, };

	// queue를 지역 변수로 선언했기에 초기화 필요 X
	queue <pair<int, int>> Q;

	Q.push({ sx,sy }); visited[sx][sy] = 1;
	while (!Q.empty()) {
		x = Q.front().first, y = Q.front().second, cnt = visited[x][y];
		Q.pop();

		for (int i = 0; i < 8; i++) {
			nx = x + move[i][0], ny = y + move[i][1];

			// 체스판 밖이거나 이미 방문했다면 통과
			if (nx < 0 || nx >= l || ny < 0 || ny >= l || visited[nx][ny]) continue;

			// 이동하려는 칸 도착 시 함수 종료 ( 시작값을 1로 잡았기에 cnt++ X)
			if (nx == ex && ny == ey) return cnt;

			Q.push({ nx,ny });
			visited[nx][ny] = cnt + 1;
		}
	}
}

int main() {
	int T, sx, sy, ex, ey;
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		scanf("%d", &l);
		scanf("%d %d\n%d %d", &sx, &sy, &ex, &ey);
		printf("%d\n", Moving(sx, sy, ex, ey));
	}
	return 0;
}

'Study > Algorithm' 카테고리의 다른 글

BOJ (C/C++) 1259번: 팰린드롬수  (0) 2022.12.05
BOJ (C/C++) 12851번: 숨바꼭질 2  (0) 2022.12.04
BOJ (C/C++) 1697번: 숨바꼭질  (0) 2022.12.04
BOJ (C/C++) 6593번: 상범 빌딩  (0) 2022.12.04
BOJ (C/C++) 5567번: 결혼식  (0) 2022.12.03