[백준] 7562번: 나이트의 이동
📝문제
평소에 풀던 것보다 쉬운 난이도의 문제라 그런지 쉽게 풀 수 있었다.
보자마자 BFS 문제다 싶었고, 머리 속에 떠올렸던 로직을 바로 구현하여 해결했다.
📌코드
package Baekjoon;
import java.util.*;
import java.io.*;
public class BOJ7562 {
static int t;
//나이트가 이동할 수 있는 방향
static int[] moveY = {-1, -2, -2, -1, 1, 2, 2, 1};
static int[] moveX = {-2, -1, 1, 2, 2, 1, -1, -2};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
t = Integer.parseInt(st.nextToken());
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int[][] visited = new int[l][l]; //각 칸에 최소 몇 번으로 도달했는지 기록한다
st= new StringTokenizer(br.readLine());
int startY = Integer.parseInt(st.nextToken());
int startX = Integer.parseInt(st.nextToken());
st= new StringTokenizer(br.readLine());
int endY = Integer.parseInt(st.nextToken());
int endX = Integer.parseInt(st.nextToken());
Queue<int[]> q= new LinkedList<>();
q.add(new int[] {startY, startX});
while(!q.isEmpty()){
int[] curPnt = q.poll();
int curY = curPnt[0];
int curX = curPnt[1];
if(curX == endX && curY == endY) {
System.out.println(visited[curY][curX]);
break;
}
for(int j = 0; j < 8; j++){
int nextY = curY + moveY[j];
int nextX = curX + moveX[j];
//이전 칸의 수에서 1씩 더해준다
//범위 검사
if(nextX < 0 || nextX >= l || nextY < 0 || nextY >= l) continue;
if(visited[nextY][nextX] != 0) continue;
q.add(new int[] {nextY, nextX});
visited[nextY][nextX] = visited[curY][curX] + 1;
}
}
}
}
}
Author And Source
이 문제에 관하여([백준] 7562번: 나이트의 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@paulus0617/boj7562
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
package Baekjoon;
import java.util.*;
import java.io.*;
public class BOJ7562 {
static int t;
//나이트가 이동할 수 있는 방향
static int[] moveY = {-1, -2, -2, -1, 1, 2, 2, 1};
static int[] moveX = {-2, -1, 1, 2, 2, 1, -1, -2};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
t = Integer.parseInt(st.nextToken());
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int[][] visited = new int[l][l]; //각 칸에 최소 몇 번으로 도달했는지 기록한다
st= new StringTokenizer(br.readLine());
int startY = Integer.parseInt(st.nextToken());
int startX = Integer.parseInt(st.nextToken());
st= new StringTokenizer(br.readLine());
int endY = Integer.parseInt(st.nextToken());
int endX = Integer.parseInt(st.nextToken());
Queue<int[]> q= new LinkedList<>();
q.add(new int[] {startY, startX});
while(!q.isEmpty()){
int[] curPnt = q.poll();
int curY = curPnt[0];
int curX = curPnt[1];
if(curX == endX && curY == endY) {
System.out.println(visited[curY][curX]);
break;
}
for(int j = 0; j < 8; j++){
int nextY = curY + moveY[j];
int nextX = curX + moveX[j];
//이전 칸의 수에서 1씩 더해준다
//범위 검사
if(nextX < 0 || nextX >= l || nextY < 0 || nextY >= l) continue;
if(visited[nextY][nextX] != 0) continue;
q.add(new int[] {nextY, nextX});
visited[nextY][nextX] = visited[curY][curX] + 1;
}
}
}
}
}
Author And Source
이 문제에 관하여([백준] 7562번: 나이트의 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@paulus0617/boj7562저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)