7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class XY{
int x; int y;
public XY(int x, int y){
this.x = x; this.y = y;
}
}
static int[] dx = {-2, -2, -1, 1, 2, 2, 1, -1};
static int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};
static int n;
static int[][] chess;
static boolean[][] visited;
static XY end; //도착 지점
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testcase = Integer.parseInt(br.readLine());
for(int i=0; i<testcase; i++){
n = Integer.parseInt(br.readLine());
visited = new boolean[n][n];
chess = new int[n][n];
StringTokenizer st1 = new StringTokenizer(br.readLine());
XY start = new XY(Integer.parseInt(st1.nextToken()),Integer.parseInt(st1.nextToken()));
st1 = new StringTokenizer(br.readLine());
end = new XY(Integer.parseInt(st1.nextToken()),Integer.parseInt(st1.nextToken()));
bfs(start.x, start.y);
System.out.println(chess[end.x][end.y]);
}
}
private static void bfs(int a, int b){
Queue<XY> q = new LinkedList<>();
q.offer(new XY(a,b));
visited[a][b] = true;
if(a==end.x && b==end.y)
return;
while(!q.isEmpty()){
int x = q.peek().x;
int y = q.peek().y;
q.poll();
for(int i=0; i<8; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < n) {
if (!visited[xx][yy]){
q.offer(new XY(xx,yy));
visited[xx][yy] = true;
chess[xx][yy] = chess[x][y]+1;
}
}
}
}
}
}
나이트가 이동할 수 있는 위치는 다음의 8가지 경우이다.
시작 위치 에서부터 도착 위치까지 bfs 탐색을 한다.
도착 위치까지만 가면 되므로, chess[][] 배열은 0으로 채워진(초기화된) 상태로 bfs 탐색을 한다.
나이트가 이동할 때마다 == 큐에 push할 때마다
chess[xx][yy] = chess[x][y]+1 을 해준다. 즉, 이전 위치에 +1해서 넣어준다.
- n=8, start(0,0), end(7,0) 일때, bfs탐색 후의 chess[][] 는 다음과 같이 된다.
'1d-1c > BOJ' 카테고리의 다른 글
1759_암호 만들기 (JAVA) (0) | 2020.11.18 |
---|---|
2309_일곱 난쟁이 (JAVA) (0) | 2020.11.18 |
2529_부등호 (JAVA) (0) | 2020.11.17 |
10026_적록색약 (JAVA) (0) | 2020.11.16 |
10819_차이를 최대로 (JAVA) (0) | 2020.11.15 |