[Baekjoon] 18404_현명한 나이트

Silver I

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

---

< 현명한 나이트 >

 

문제 풀이 

 

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 _18404_ { // 현명한 나이트
	static boolean visited[][];
	static int arr[][], result[], n, cnt;
	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 bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		visited = new boolean[n][n];
		cnt = 0;

		st = new StringTokenizer(bf.readLine());
		int x = Integer.parseInt(st.nextToken()) - 1;
		int y = Integer.parseInt(st.nextToken()) - 1;

		arr = new int[m][2];
		result = new int[m];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			arr[i][0] = a;
			arr[i][1] = b;
		}

		bfs(x, y);

		for (int i = 0; i < m; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
	}

	private static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y, 0 });
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				int a = temp[0] + dx[i];
				int b = temp[1] + dy[i];
				if (a >= 0 && a < n && b >= 0 && b < n && !visited[a][b]) {
					visited[a][b] = true;
					for (int j = 0; j < arr.length; j++) {
						if (a == arr[j][0] && b == arr[j][1]) {
							result[j] = temp[2] + 1;
							cnt += 1;
							break;
						}
					}
					queue.add(new int[] { a, b, temp[2] + 1 });
				}
				if (cnt == result.length)
					break;
			}
			if (cnt == result.length)
				break;
		}
	}
}

 

Main

변수)
n : 체스판 크기
m : 상대편 말의 개수
visited : 방문 여부
cnt : 상대편 말 잡은 수
x, y : 나이트의 위치
arr : 상대편 말 위치 저장
result : 상대편 말을 잡기 위한 최소 이동 수 저장
a, b : 상대편 말의 위치

 

- 체스판의 크기(n), 상대편 말의 개수(m) 입력

- 나이트의 위치 (x, y) 입력

- m개의 줄에 걸쳐 상대편의 말의 위치(a, b)를 입력받아 저장

- bfs 함수 호출

- 정답(result) 출력

 

bfs

- queue에 저장 [x, y, 이동 수]

- queue가 빌 때까지 반복

: 8가지 방향으로 이동하여 체스판 범위 안이며 아직 방문하지 않았다면 방문 표시 및 queue에 저장

: 이동한 위치가 상대편 말이 있는 위치라면 최소 이동 수 저장 

---

---