[백준] 7562번 나이트의 이동 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
24. DFS와 BFS
그래프를 순회하는 알고리즘을 배워 봅시다.
그래프를 순회하는 알고리즘을 배워 봅시다.
Java / Python
10. 나이트의 이동
나이트를 목적지까지 이동시키는 문제
이번 문제는 나이트를 목적지까지 이동시키는 문제입니다. 체스판 위 나이트를 몇번 움직이면 목적지 칸까지 이동할 수 있는지 구하는 문제입니다.
BFS 탐색을 이용했습니다.
- Java
import java.io.*;
import java.util.*;
public class Main {
static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
static int N;
static int cnt = 0;
static int[][] map;
static boolean[][] check;
static int start_x, start_y, end_x, end_y;
// 나이트가 이동할 수 있는 경우의 수
static int[] dx = {-2,-1,2,1,2,1,-2,-1};
static int[] dy = {1,2,1,2,-1,-2,-1,-2};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
check = new boolean[N][N];
StringTokenizer st = new StringTokenizer(br.readLine());
start_x = Integer.parseInt(st.nextToken());
start_y = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
end_x = Integer.parseInt(st.nextToken());
end_y = Integer.parseInt(st.nextToken());
bfs(new Point(start_x,start_y));
bw.write(map[end_x][end_y] + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static void bfs(Point p) {
Queue<Point> queue = new LinkedList<>();
if(p.x == end_x && p.y == end_y) return;
queue.add(p);
check[p.x][p.y] = true;
while (!queue.isEmpty()) {
Point pt = queue.poll();
if(pt.x == end_x && pt.y == end_y) {
return;
}
for (int i = 0; i < 8; i++) {
int nx = pt.x + dx[i];
int ny = pt.y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !check[nx][ny]) {
queue.add(new Point(nx, ny));
check[nx][ny] = true;
map[nx][ny] = map[pt.x][pt.y] + 1;
}
}
}
}
}
- Python
from collections import deque
import sys
T = int(sys.stdin.readline())
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
# bfs 경로 탐색
def bfs(sx, sy, ex, ey):
queue = deque()
queue.append([sx, sy])
place[sx][sy] = 1
while queue:
a, b = queue.popleft()
if a == ex and b == ey:
print(place[ex][ey] - 1)
return
for i in range(8):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < N and 0 <= y < N and place[x][y] == 0:
place[x][y] = place[a][b] + 1
queue.append([x, y])
for _ in range(T):
N = int(sys.stdin.readline())
sx, sy = map(int, sys.stdin.readline().split())
ex, ey = map(int, sys.stdin.readline().split())
place = [[0]* N for _ in range(N)]
bfs(sx, sy, ex, ey)
Author And Source
이 문제에 관하여([백준] 7562번 나이트의 이동 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-7562번-나이트의-이동-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)