<BOJ>7562번: 나이트의 이동
문제
접근
- BFS의 틀을 알면 바로 풀 수 있는 문제 중의 하나다.
dx[], dy[]
로 나이트의 이동 방향을 미리 초기화 한다.- Flood Fill을 통해 목표 지점까지의 거리를 계산하면 된다.
내 코드
import java.io.*;
import java.util.*;
public class Main {
static StringTokenizer st;
static int[] dx = {1,2,2,1,-1,-2,-2,-1};
static int[] dy = {-2,-1,1,2,2,1,-1,-2};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
while (tc-- > 0) {
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
st = new StringTokenizer(br.readLine());
Node start = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
st = new StringTokenizer(br.readLine());
Node end = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
bfs(arr, start, end);
}
}
public static void bfs(int[][] dist, Node start, Node end) {
Queue<Node> q = new LinkedList<>();
boolean[][] isVisited = new boolean[dist.length][dist.length];
q.add(start);
isVisited[start.getX()][start.getY()] = true;
while (!q.isEmpty()) {
Node cur = q.poll();
if (cur.getX() == end.getX() && cur.getY() == end.getY()) {
System.out.println(dist[cur.getX()][cur.getY()]);
return;
}
for (int i = 0; i < 8; i++) {
int nx = cur.getX() + dx[i];
int ny = cur.getY() + dy[i];
if (nx >= 0 && nx < dist.length && ny >= 0 && ny < dist.length && !isVisited[nx][ny]) {
isVisited[nx][ny] = true;
dist[nx][ny] = dist[cur.getX()][cur.getY()] + 1;
q.add(new Node(nx, ny));
}
}
}
}
static class Node {
private int x; private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
}
Author And Source
이 문제에 관하여(<BOJ>7562번: 나이트의 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@songs4805/BOJ7562번-나이트의-이동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)