[Baekjoon] 8598_Zając

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

---

< Zając >

 

문제 풀이 

 

bfs를 사용하여 이동 횟수를 구한다.

 

 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 _8598_ { // Zając
	static int dx[] = { 1, 1, -1, -1, 2, 2, -2, -2 };
	static int dy[] = { 2, -2, 2, -2, 1, -1, 1, -1 };
	static boolean arr[][];
	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());
		arr = new boolean[n][m];
		int x1 = -1, x2 = -1, y1 = -1, y2 = -1;
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				if (str.charAt(j) == 'x') {
					arr[i][j] = true;
				} else if (str.charAt(j) == 'z') {
					x1 = i;
					y1 = j;
				} else if (str.charAt(j) == 'n') {
					x2 = i;
					y2 = j;
				}
			}
		}
		int result = bfs(x1, y1, x2, y2);
		if (result == -1) {
			System.out.println("NIE");
		} else {
			System.out.println(result);
		}
	}
	private static int bfs(int x1, int y1, int x2, int y2) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x1, y1, 0 });
		arr[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 < arr.length && y >= 0 && y < arr[0].length && !arr[x][y]) {
					if (x == x2 && y == y2) {
						return temp[2] + 1;
					}
					arr[x][y] = true;
					queue.add(new int[] { x, y, temp[2] + 1 });
				}
			}
		}
		return -1;
	}
}

변수)
dx, dy : 8방향
arr : 배열
n, m : 배열 크기
x1, x2, y1, y2 : 시작 위치, 도착 위치

 

배열 크기를 입력받아 배열 크기만큼 배열 정보를 입력받는다. 값이 x인 경우 true로 저장하고 z와 n인 경우 위치를 저장한다. bfs함수를 호출한 후 값이 -1인 경우 NIE를 아닌 경우 result를 출력한다.

 

bfs(시작 위치, 도착 위치)

큐에 시작 좌표를 저장한 후 큐가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

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

 

도착 위치에 도달하지 못한다면 -1을 반환한다.

---

---