Search
Duplicate
🙆🏻‍♀️

데스 나이트

주차
16
문제번호
16948
언어
티어
실버
유형
BFS
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

메모리

시간

1264 KB
0 ms

Code

#include <cstdio> #include <queue> using namespace std; int main() { int n; scanf("%d", &n); int map[200][200] = {0,}; int result; int r1,c1,r2,c2; scanf("%d%d%d%d", &r1, &c1, &r2, &c2); queue <pair<int, int> > queue; int mov_r[6] = {-2, -2, 0, 0, 2, 2}; int mov_c[6] = {-1, 1, -2, 2, -1, 1}; queue.push(make_pair(r1,c1)); while (!queue.empty()) { result = 0; for (int i = 0; i < 6; i++) { int rr = queue.front().first + mov_r[i]; int cc = queue.front().second + mov_c[i]; if(rr >= 0 && rr < n && cc >= 0 && cc < n) { if (map[rr][cc]) continue ; map[rr][cc] = map[queue.front().first][queue.front().second] + 1; if (rr == r2 && cc == c2) { printf("%d", map[rr][cc]); return 0; } queue.push(make_pair(rr,cc)); } } queue.pop(); } printf("%d", -1); return 0; }
C++
복사

문제 풀이

체스판에서 r, c 가 이동할 수 있는 경우는 총 6가지가 있다.
mov_r , mov_c 배열을 사용하여 인덱스를 움직여주고 queue<pair> 를 사용해서 방문한 인덱스 체크와 counting 을 함께 해주었다.
만약 움직일 수 있는 다음칸이 체스판 내에 있다면 방문여부를 체크 후 움직인 칸에 count + 1 을 헤주고
만약 도달해야할 칸에 도달 했다면 해당 값 출력을 한다.
만약 다음 방문할 칸이 체스판 범위를 넘어가면 continue , 큐에 넣지 않고 다음 칸을 체크한다.
큐에 값이 비었다면 해당 칸에 갈 수 없음으로 -1 출력을 한다.