Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

10. 나이트의 이동

7562번

나이트를 목적지까지 이동시키는 문제

이번 문제는 나이트를 목적지까지 이동시키는 문제입니다. 체스판 위 나이트를 몇번 움직이면 목적지 칸까지 이동할 수 있는지 구하는 문제입니다.
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)