[BAEKJOON]7562 나이트의 이동

문제 요약

• 알고리즘 분류: bfs, 구현, 시물레이션
• 난이도:Silver1
• 문제내용:
  • 테스트 케이스 개수가 주어진다
  • 각 테스트 케이스마다 한변의  정사각형 길이, 시작점, 도착점을 준다.
  • 나이트가 시작점에 도착점까지 최소 이동을 구해라

• 사이트: https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제풀이

 이번 문제는 BFS 탐색 문제이다.  BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

 기존 BFS는 각 노드간의 탐색인데 이번에는 2차원 배열로 응용한 BFS 탐색이다. 노드 대신 2차원 배열로 변경 된것만 생각하면 된다.

문제 접근 방법

 이번 문제의 주는 BFS + 시물레이션 2개를 구현 해야 한다. 일단 시물레이션은 어떻게 구현 해야 하는지 부터 봐야 한다.

나이트 이동할수 있는 위치

 우선 나이트가 이동 할수 있는 위치를 알아야 한다. 나이트 이동하는 방향은 앞/뒤/좌/ 우으로 2칸  + 이동하는 대각선 1칸이고 이동할수 있는 범위는 총 8가지가 나오고 좌표는 위 그림으로 표현 할수 있다.  그러면 좌표는 아래와 같이 표현이 가능하다.

{{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2 , 1}}

 

위 8가지 방향으로 범위 안에 이동을 하면된다.

시뮬레이션 부분은 끝났으니 그 다음은 BFS 탐색을 구현만 하면된다. 기존 BFS는 방문 여부를 체크해서 처리를 했다면 이번 문제에서는 2차원 배열을 방문여부를 체크해서 나가면 된다. 근데 2차원 방문 여부 배열을 만들려고 하니까 또 새로 만들어야 하는것은 아니다. 최소 방문 개수라서 모든 2차원 배열은 0으로 시작해서 방문 했을때 0일 때만 아래 그림처럼 이전 방문에 +1씩 해주기만 하면된다. 탐색이 끝났으면 도착점 개수를 출력만 해주면 끝이다.

정리

1. 나이트 8개 좌표를 선언한다.
2. 2차원 배열을 선언후 모두 0으로 초기화 한다.
3. 시작점 부터 8개 좌표로 이동하면서 BFS 탐색을 한다.
4. 2차원 배열 범위 안이고 0일때 이전 방문한 좌표값에서 + 1을해준다.

Code

Python

import sys
from collections import deque
input = sys.stdin.readline

# 나이트 이동할수 있는 좌표
dx = [-2, -2, -1, -1, 1, 1, 2, 2] 
dy = [-1, 1, -2, 2, -2, 2, -1, 1]

def dfs(n):
    fields = [[0] * n for i in range(n)]
    queue = deque([start])
    while queue:
        x, y = queue.popleft()
        if end == [x, y]:
            break
        for i in range(8):
            fx, fy = x + dx[i], y + dy[i]
            if 0<= fx < n and 0 <= fy < n and fields[fx][fy] == 0:
                fields[fx][fy] = fields[x][y] + 1
                queue.append((fx, fy))
    return fields[end[0]][end[1]]

for _ in range(int(input())):
    size = int(input())
    start = list(map(int, input().split()))
    end = list(map(int, input().split()))
    print(dfs(size))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	// 나이트 이동할수있는 좌표
	static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2}; 
	static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[] start, end;
		int size;
		while(N-- > 0) {
			size = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());			
			start = new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
			st = new StringTokenizer(br.readLine());
			end = new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
			System.out.println(bfs(size, start, end));
		}
		
	}
	
	public static int bfs(int size, int[] start, int[] end) {
		int[][] fields = new int[size][size];
		Queue<int[]> queue =  new LinkedList<int[]>();
		queue.add(start);
		int x, y, fx, fy;
		int[] location;
		while (!queue.isEmpty()) {
			location = queue.poll();
			x = location[0];
			y = location[1];
			if(x == end[0] && y == end[1]) break;
			for(int i = 0; i < 8; i++) {
				fx = x + dx[i];
				fy = y + dy[i];
				// 필드 범위 안이거나 방문 하지 않았을 경우
				if(0 <= fx && fx < size && 0<= fy && fy < size && fields[fx][fy] == 0) {
					fields[fx][fy] = fields[x][y] + 1;
					queue.add(new int[] {fx, fy});
				}
			}
		}
		
		return fields[end[0]][end[1]];
	}

}