[Baekjoon] 1331_나이트 투어

Silver IV

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

---

< 나이트 투어 >

 

문제 풀이 

 

나이트가 경로로 이동 가능한지 판단한다. 모든 칸을 정확히 한 번씩 방문해야 하므로 이미 방문한 곳에는 갈 수 없다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _1331_ { // 나이트 투어
	static Queue<int[]> queue;
	static boolean arr[][];

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

		arr = new boolean[6][6];

		int startX = 0, startY = 0;
		queue = new LinkedList<>();

		for (int i = 0; i < 36; i++) {
			String str = bf.readLine();
			int x = 0;
			int y = 6 - (str.charAt(1) - '0');

			if (str.charAt(0) == 'A') {
				x = 0;
			} else if (str.charAt(0) == 'B') {
				x = 1;
			} else if (str.charAt(0) == 'C') {
				x = 2;
			} else if (str.charAt(0) == 'D') {
				x = 3;
			} else if (str.charAt(0) == 'E') {
				x = 4;
			} else if (str.charAt(0) == 'F') {
				x = 5;
			}

			if (i == 0) {
				startX = x;
				startY = y;
			}
			queue.add(new int[] { x, y });
		}
		queue.add(new int[] { startX, startY });

		if (check(queue)) {
			System.out.println("Valid");
		} else {
			System.out.println("Invalid");
		}
	}

	private static boolean check(Queue<int[]> queue) {
		int dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
		int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };

		int now[] = queue.poll();
		boolean flag = false;

		while (!queue.isEmpty()) {
			for (int i = 0; i < 8; i++) {
				int x = now[0] + dx[i];
				int y = now[1] + dy[i];
				if (queue.peek()[0] == x && queue.peek()[1] == y) {
					if (arr[x][y]) {
						return false;
					}
					arr[x][y] = true;
					flag = true;
					now = queue.poll();
					break;
				}
			}
			if (!flag) {
				return false;
			}
			flag = false;
		}
		return true;
	}
}

변수)
arr : 체스판 방문 여부
startX, startY : 시작 위치
queue : 나이트 방문 경로
str : 방문 위치
x, y : 방문 위치를 숫자로 변환

 

36 개줄에 걸쳐 나이트의 방문 위치를 입력받는다. A-F를 각 0-5로 치환하고 1-6을 5-0으로 치환하여 queue에 저장한다. 첫 번째 방문 위치를 기억해 뒀다 마지막에 다시 queue에 추가한다. 그 후 check 함수를 통해 나이트의 경로를 확인하고 올바른 것이면 Valid를 올바르지 않은 경로면 Invalid를 출력한다.

 

check (Queue <int []> queue)

queue에서 poll 하여 시작 위치를 now에 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

 

1) 나이트가 이동할 수 있는 8방향의 좌표를 구한 후 그 좌표가 queue의 peek 값과 일치하는지 확인한다.

2) 일치하면 방문 여부를 살펴본다. 이미 방문한 곳이라면 false를 반환한다. 아직 방문하지 않은 곳이라면 방문 표시 후 queue에서 poll 한 값으로 현재 위치를 업데이트한 후 다시 1)로 돌아간다.

3) 8방향 좌표 모두 queue의 peek 값과 일치하지 않다면 올바르지 않은 나이트 경로이므로 false를 반환한다.

 

queue가 비었다면 나이트의 올바른 경로이므로 true를 반환한다.

---

---