[Baekjoon] 15242_Knight

문제(출처: https://www.acmicpc.net/problem/15242)

---

< Knight >

 

문제 풀이 

 

bfs 알고리즘을 활용한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class _15242_ { // Knight
	static int dx[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
	static int dy[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
		String start = bf.readLine();
		String end = bf.readLine();
        
		int x1 = 8 - (start.charAt(1)-'0');
		int y1 = start.charAt(0) - 'a';
        
		int x2 = 8 - (end.charAt(1)-'0');
		int y2 = end.charAt(0) - 'a';
        
		if (x1 == x2 && y1 == y2) {
			System.out.println(0);
		} else {
			System.out.println(bfs(x1, y1, x2, y2));
		}
	}
	private static int bfs(int x1, int y1, int x2, int y2) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x1, y1, 0 });
        
		boolean visited[][] = new boolean[8][8];
		visited[x1][y1] = true;
        
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < 8 && y >= 0 && y < 8 && !visited[x][y]) {
					if (x == x2 && y == y2) {
						return temp[2] + 1;
					}
					visited[x][y] = true;
					queue.add(new int[] { x, y, temp[2] + 1 });
				}
			}
		}
		return -1;
	}
}

변수)
start, end : 출발 위치, 도착 위치
x1, y1, x2, y2 : 출발 위치, 도착 위치를 좌상단에 맞춰 변경

 

출발 위치와 도착 위치를 입력받는다. 현재 입력된 위치는 좌하단 기준이므로 좌상단에 맞춰 변경하여 x1, y1, x2, y2에 저장한다. 출발 위치와 도착 위치가 같다면 0을 출력하고 같지 않다면 bfs 함수를 호출한다.

 

bfs(int x1, int y1, int x2, int y2)

Queue에 시작 위치와 이동 횟수를 저장하며 시작 위치를 방문처리한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 8방향으로 탐색 후 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 Queue에 추가. 만약 이동 위치가 도착 위치라면 temp[2]+1을 반환한다.

 

---

---