#7562 나이트의 이동
난이도 : 실버 2
유형 : 그래프 탐색
▸ 문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
▸ 입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
▸ 출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
문제 풀이 🖋
해당 문제는 나이트 이동 방향 8가지의 경우를 모두 BFS 탐색해주면 된다.
📚 조건
∙ 체스판 한 변의 길이 l (4<= l <= 300)
∙ 체스판의 크기 | x |
∙ 체스팍 각 칸은 두수의 쌍 {0, ..., l-1} × {0, ..., l-1}으로 나타낸다.
∙ 이동방향 총 8가지
→ dx = {-2, -1, 2, 1, 2, 1, -2, -1}
→ dy = {1, 2, 1, 2, -1, -2, -1, -2}
풀이 코드 ✔︎
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {-2,-1,2,1,2,1,-2,-1};
static int[] dy = {1,2,1,2,-1,-2,-1,-2};
static boolean[][] visited;
static int[][] memo;
static int len;
static int e_x, e_y;
static Queue<Pos> q = new LinkedList<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for(int t=0; t<tc; t++) {
len = Integer.parseInt(br.readLine());
memo = new int[len][len];
visited = new boolean[len][len];
StringTokenizer st = new StringTokenizer(br.readLine());
int s_x = Integer.parseInt(st.nextToken());
int s_y = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
e_x = Integer.parseInt(st.nextToken());
e_y = Integer.parseInt(st.nextToken());
bfs(new Pos(s_x, s_y));
System.out.println(memo[e_x][e_y]);
}
}
static void bfs(Pos nPos) {
if(nPos.x == e_x && nPos.y == e_y) {
return;
}
visited[nPos.x][nPos.y] = true;
q.add(nPos);
while(!q.isEmpty()) {
Pos p = q.poll();
int x = p.x;
int y = p.y;
for(int i=0; i<dx.length; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=0 && nx<len && ny>=0 && ny<len && !visited[nx][ny]) {
q.add(new Pos(nx,ny));
visited[nx][ny] = true;
//전의 이동 횟수에 +1 씩 더해주며 이동 횟수를 증가시켜준다.
memo[nx][ny] = memo[x][y] + 1;
}
}
}
}
}
class Pos{
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 10942번 펠린드롬? (Java) (0) | 2021.05.23 |
---|---|
[BOJ] 백준 15486번 퇴사 2 (Java) (2) | 2021.05.22 |
[BOJ] 백준 2589번 보물섬 (Java) (0) | 2021.05.21 |
[BOJ] 백준 2688번 줄어들지 않아 (Java) (0) | 2021.05.21 |
[BOJ] 백준 5014번 스타트링크 (Java) (0) | 2021.05.20 |