-
백준(BOJ) 16948번 데스 나이트알고리즘 풀이/백준(Boj) 2019. 11. 7. 13:49
문제 : https://www.acmicpc.net/problem/16948
16948번: 데스 나이트
게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부
www.acmicpc.net
풀이 :
기본적인 BFS 문제였습니다. 첫 시작 구간을 fy, fx로 잡고 나아갈 수 있는 6방향을 확인합니다.
탐색을 끝내고 ey, ex 구간을 지났다면 그 최소구간을 출력하고 구간을 지나지 않았다면 -1을 출력합니다.
코드 ( C++ )
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters#include <iostream> #include <queue> #include <cstring> using namespace std; const int dy[6] = { -2,-2,0,0,2,2 }; const int dx[6] = { -1,1,-2,2,-1,1 }; int d[201][201]; int main() { int n; cin >> n; int fy, fx, ey, ex; cin >> fy >> fx >> ey >> ex; memset(d, -1, sizeof(d)); queue<pair<int, int>> q; q.push({ fy,fx }); d[fy][fx] = 0; while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int i = 0; i < 6; ++i) { int ny = y + dy[i]; int nx = x + dx[i]; if (!(0 <= ny && ny < n && 0 <= nx && nx < n)) continue; if (d[ny][nx] == -1) { d[ny][nx] = d[y][x] + 1; q.push({ ny,nx }); } } } if (d[ey][ex] == -1) cout << -1 << "\n"; else cout << d[ey][ex] << "\n"; return 0; } '알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 14890번 경사로 (0) 2019.11.16 백준(BOJ) 17135번 캐슬 디펜스 (0) 2019.11.13 백준(BOJ) 16926번 배열 돌리기 1 (0) 2019.11.04 백준(BOJ) 16928번 뱀과 사다리 게임 (31) 2019.11.01 백준(BOJ) 17070번 파이프 옮기기 1 (31) 2019.10.31