[Baekjoon] 6601_Knight Moves

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

---

< Knight Moves >

 

문제 풀이 

 

bfs 알고리즘을 활용한다.

 

 my solution (Java)

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

public class _6601_ { // Knight Moves
	static int dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
	static int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
        
		String str = "";
		while ((str = bf.readLine()) != null) {
			st = new StringTokenizer(str);
            
			String start = st.nextToken();
			String end = st.nextToken();
            
			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) {
				bw.write("To get from " + start + " to " + end + " takes 0 knight moves.\n");
			} else {
				bw.write("To get from " + start + " to " + end + " takes " + bfs(x1, y1, x2, y2) + " knight moves.\n");
			}
		}
		bw.flush();
	}
    
	private static int bfs(int x1, int y1, int x2, int y2) {
		boolean visited[][] = new boolean[8][8];
		visited[x1][y1] = true;
        
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x1, y1, 0 });
        
		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;
	}
}

변수)
x1, y1, x2, y2 : 출발 위치, 도착 위치를 좌상단에 맞춰 변경
dx, dy : 이동 방향
visited : 방문 여부

 

출발 위치와 도착 위치를 입력받는다. 현재 입력된 위치는 좌하단 기준이므로 좌상단에 맞춰 변경하여 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을 반환한다.

 

---

---