[Baekjoon] 7107_Journey of A Knight

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

---

< Journey of A Knight >

 

문제 풀이 

 

bfs를 활용해 (i, j) 위치로 이동할 수 있는지 확인한다.

 

 my solution (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 _7107_ { // Journey of A Knight
	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));
		StringTokenizer st = new StringTokenizer(bf.readLine());
        
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int i = Integer.parseInt(st.nextToken()) - 1;
		int j = m - Integer.parseInt(st.nextToken());
        
		boolean arr[][] = new boolean[m][n];
		int x = m - 1, y = 0;
		arr[x][y] = true;
        
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y, 0 });
        
		boolean flag = false;
		int result = -1;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 8; k++) {
				x = temp[0] + dx[k];
				y = temp[1] + dy[k];
				if (x >= 0 && x < m && y >= 0 && y < n && !arr[x][y]) {
					if (x == j && y == i) {
						flag = true;
						result = temp[2] + 1;
						break;
					}
					arr[x][y] = true;
					queue.add(new int[] { x, y, temp[2] + 1 });
				}
			}
			if (flag) {
				break;
			}
		}
        
		if (result != -1) {
			System.out.println(result);
		} else {
			System.out.println("NEVAR");
		}
	}
}

 

변수)
dx, dy : 이동 방향
n, m : 배열 크기
i, j : 도착 위치
arr : 배열
x, y : 현재 위치
flag : 도착 가능 여부
result : 도착 가능한 최소 횟수

 

배열 크기 n, m과 도착 위치 i, j를 입력받는다. 출발 위치를 (m-1, 0)으로 초기화하고 배열 값을 true로 저장한다. Queue에 시작 위치와 이동 횟수를 저장한 뒤 queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 8방향으로 이동 후 배열 범위 안이며 아직 방문하지 않았다면 방문 표시 및 queue에 추가

3) 만약 이동한 위치가 도착 위치라면 종료

 

result 값이 -1이 아니라면 result 출력, -1이라면 "NEVAR" 출력

---

---