문제
https://www.acmicpc.net/problem/7562
풀이
방문한 순서대로 좌표를 저장하기 위한 데이터 타입으로 pair를 가지는 queue를 선언했다.
std::queue<std::pair<int, int>> q;
🔍 knight()
- 처음 함수를 실행하면 (0, 0)에서 방문할 수 있는 위치들를 탐색하여 목표 지점에 왔는지 확인한다.
- 첫번째 이동으로 갈 수 있는 모든 위치를 queue에 저장한다.
- 이 때, 재방문 방지를 위해 min[x][y] == 0 이라는 조건을 달아주었다. (한번도 방문 안한 곳이라면 queue에 넣는다.)
- queue에는 다음 이동으로 갈 수 있는 모든 위치를 갖게 된다.
이 과정을 (N, M)까지 반복한다. (N, M)에 도달하면 바로 return 하기 때문에 최소 이동 횟수을 바로 알 수 있다. (BFS 특성)
- 채점 데이터는 무조건 (N, M)에 갈 수 있도록 주어졌지만 혹시나해서 while(!q.empty())라는 조건을 달아주었다.
🚩주의할 점
#include <memory.h>
// ..
memset(min, 0, sizeof(min));라이브러리 추가 잊지 않기
bool isValidRange(int a, int b)
{
if(a <l && b <l && a >= 0 && b >= 0)
return true;
return false;
}
체스판 이동을 해줄 때 반드시 범위 체크를 해주어야 한다.
a <= l가 아니라 a < l 이라는 점을 유의.
소스
#include <iostream> #include <memory.h> // memset #include <queue> #define MAX 302 int min[MAX][MAX]; int X, Y = 0; // 현재 좌표 int N, M = 0; // 목표 좌표 int l = 0; bool isValidRange(int a, int b) { if(a <l && b <l && a >= 0 && b >= 0) return true; return false; } void knight(int _x, int _y) { //BFS std::queue<std::pair<int, int>> q; q.push(std::make_pair(_x, _y)); int xPos[8] = {2, 1, -1, -2, -2, -1, 1, 2}; int yPos[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; while(!q.empty()) { int nowX = q.front().first; int nowY = q.front().second; if(nowX == N && nowY == M) return; q.pop(); for(int i=0; i<8; ++i) { int x = nowX + xPos[i]; int y = nowY + yPos[i]; if(!isValidRange(x, y)) continue; if(min[x][y] == 0 || min[x][y] > min[nowX][nowY]+ 1) { min[x][y] = min[nowX][nowY] + 1; q.push(std::make_pair(x, y)); } } } } int main() { int T = 0; std:: cin >> T; while(T--) { std::cin >> l >> X >> Y >> N >> M; memset(min, 0, sizeof(min)); knight(X, Y); std::cout << min[N][M] << "\n"; } return 0; } | cs |
+ tmi
더보기
DFS로 풀었다가 시간 초과를 봤습니다. 왜 DFS로는 안될까 검색을 하다가 아래 글을 봤습니다.
그래서 BFS로 풀었습니다.
'최소'라는 용어가 나오면
BFS로 풀어야합니다.
마찬가지로 미로찾기 같이 '최소'의 수로 빠져나와야 한다던지
그런 느낌의 문제는 전부 BFS로 접근하시면 됩니다.
[출처] [자바] 백준 7562 : 나이트의 이동 (BFS 문제 풀어보기)|작성자 sosow0212
#include <iostream> #include <memory.h> // memset #define MAX 302 int min[MAX][MAX]; int X, Y =0; // 현재 좌표 int N, M = 0; // 목표 좌표 int l =0; bool isValidRange(int a, int b) { if(a <=l && b <=l && a >= 0 && b >= 0) return true; return false; } void knight(int x, int y) { if(x == N && y == M) { return; } int xPos[8] = {2, 1, -1, -2, -2, -1, 1, 2}; int yPos[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; for(int i=0; i<8; ++i) { // x, y는 현재 좌표 // r, c는 이동 가능한 좌표 int r = x + xPos[i]; int c = y + yPos[i]; //std::cout << "[TEST] r: " << r << "\tc: " << c << std::endl; if(!isValidRange(r, c)) continue; if(min[r][c] == -1 || min[r][c] > min[x][y]+ 1) { min[r][c] = min[x][y] + 1; knight(r, c); } } } int main() { int T = 0; std:: cin >> T; while(T--) { std::cin >> l >> X >> Y >> N >> M; memset(min, -1, sizeof(min)); knight(X, Y); std::cout << min[N][M] + 1 << "\n"; } return 0; } | cs |