[Baekjoon] 16509_장군

Gold V

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

---

< 장군 >

 

문제 풀이

bfs를 활용하여 상하좌우로 이동 후 대각선으로 이동할 때 조건을 설정해 준다.

 

1. 장기판 범위 안인지 확인

2. 대각선으로 이동하는 길에 다른 기물이 있는지 확인

3. 방문 여부 확인

4. 왕의 위치인지 확인

 

위와 같이 4가지의 조건을 설정해 주면 문제를 해결할 수 있었다.

 

 

 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 _16509_ {
	static int dx[] = { -1, 0, 1, 0 }; // 상 우 하 좌
	static int dy[] = { 0, 1, 0, -1 };
	static int dx2[] = { -1, -1, -1, 1, 1, 1, 1, -1 }; // 대각선
	static int dy2[] = { -1, 1, 1, 1, 1, -1, -1, -1 };
	static int r2, c2, result;
	static boolean visited[][];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		visited = new boolean[10][9];
		result = -1;

		// 상의 위치
		int r1 = Integer.parseInt(st.nextToken());
		int c1 = Integer.parseInt(st.nextToken());

		// 왕의 위치
		st = new StringTokenizer(bf.readLine());
		r2 = Integer.parseInt(st.nextToken());
		c2 = Integer.parseInt(st.nextToken());

		bfs(r1, c1, 0);

		System.out.println(result);

	}

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

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			int num = 0;
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < 10 && y >= 0 && y < 9 ) { // 장기판 범위 안
					for (int j = num; j < num+2; j++) {
						if (x + (dx2[j] * 2) >= 0 && x + (dx2[j] * 2) < 10 && y + (dy2[j] * 2) >= 0
								&& y + (dy2[j] * 2) < 9) { // 장기판 범위 안
							if (x + dx2[j] == r2 && y + dy2[j] == c2) // 다른 기물이 있으면 이동 x
								continue;
							if (visited[x + (dx2[j] * 2)][y + (dy2[j] * 2)]) 
								continue;
							if (x + (dx2[j] * 2) == r2 && y + (dy2[j] * 2) == c2) {
								result = temp[2] + 1;
								break;
							}
							visited[x + (dx2[j] * 2)][y + (dy2[j] * 2)] = true;
							queue.add(new int[] { x + (dx2[j] * 2), y + (dy2[j] * 2), temp[2] + 1 });
						}
					}
					if (result > -1)
						break;
				}
				num += 2;
			}
			if (result > -1)
				break;
		}
	}
}

 

Main

- visited : 방문 여부

- result: 최소 이동 횟수

- 상의 위치와 왕의 위치 입력 후 bfs 호출

 

bfs

- queue에 {x 좌표, y 좌표, 방문 수} 저장 및 방문 표시

- queue가 빌 때까지 반복 -> 상하좌우로 이동하여 장기판 범위 안이면 대각선으로 이동 -> 장기판 범위 안인지 확인 -> 다른 기물이 있으면 x 및 방문한 적이 있으면 x -> 대각선으로 이동한 위치가 왕의 위치라면 종료 / 왕의 위치가 아니라면 방문 표시 및 queue에 저장

 

---

생각🤔

 

대각선으로 이동했을 때 범위 조건을 잘 설정해 주면 문제를 해결할 수 있었다.

---