[Baekjoon] 10469_사이 나쁜 여왕들

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

---

< 사이 나쁜 여왕들 >

 

문제 풀이 

 

상, 하, 좌, 우, 대각선으로 제한 없이 이동했을 때 다른 여왕이 존재하는지 확인한다.

*여왕이 8개가 아니라면 올바르지 않다.

 

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 _10469_ { // 사이 나쁜 여왕들

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

		boolean visited[][] = new boolean[8][8];
		Queue<int[]> queue = new LinkedList<>();

		for (int i = 0; i < 8; i++) {
			String str = bf.readLine();
			for (int j = 0; j < 8; j++) {
				if (str.charAt(j) == '*') {
					visited[i][j] = true;
					queue.add(new int[] { i, j });
				}
			}
		}

		int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
		int dy[] = { 0, 0, -1, 1, -1, 1, -1, 1 };
		boolean flag = false;

		if (queue.size() != 8) {
			flag = true;
		}

		while (!queue.isEmpty() && !flag) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				int x = temp[0], y = temp[1];
				while (x + dx[i] >= 0 && x + dx[i] < 8 && y + dy[i] >= 0 && y + dy[i] < 8) {
					x += dx[i];
					y += dy[i];
					if (visited[x][y]) {
						flag = true;
						break;
					}
				}
				if (flag) {
					break;
				}
			}
		}

		if (flag) {
			System.out.println("invalid");
		} else {
			System.out.println("valid");
		}
	}
}

 

변수)
visited : 여왕 존재 여부
queue : 여왕 위치
str : 입력
dx, dy : 상, 하, 좌, 우, 대각선
flag : 올바른 해법 여부

 

8x8 체스판의 정보를 입력받으며 여왕이 위치한 곳이면 visited를 true로, queue에 위치를 저장한다. 만약 queue의 크기가 8이 아니라면 여왕이 8개가 아니므로 flag를 true로 저장한다. queue가 비어있지 않고 flag가 false라면 다음 과정을 반복한다.

 

1) queue poll

2) 8개의 방향으로 체스판 범위 안에 있을 때까지 이동

3) 만약 이동 위치에 다른 여왕이 있다면 flag를 true로 저장 및 종료

 

flag가 true라면 "invalid"를 출력하고 false라면 "valid"를 출력한다.

---

---