[백준] 23973번: 표적지 옮기기

문제

백준 - 23973번: 표적지 옮기기

분석

NxM 크기의 사격판에 대한 정보가 주어지고 표적지를 올려 1점부터 10점까지 정확히 한 번씩 점수를 얻을 수 있을 때, 표적지의 중심 칸이 위치해야 하는 사격판의 칸의 행과 열 번호를 구하는 문제이다.

*표적지 만들기
19x19칸에 바깥에 1을 쭉 넣어놓고 bfs 알고리즘을 이용하여 탐색하면서 안쪽까지의 거리를 기입하며 표적지를 완성했다.

scoreCount 배열에 각 1부터 10까지 각 점수를 몇 번씩 얻었는지 체크한다.
사격이 명중한 칸의 개수는 최대 100,000개라는 조건을 통해 1인 곳만 체크하면서 진행하면 시간을 줄일 수 있다.
1인 곳에서 중심이 되도록 인덱스를 조정하고, 표적지와 어긋나지 않는 경우에 한해서 scoreCount를 채워나간다. 그리고 모든 scoreCount의 값이 1인지 판별해서 가능한 경우 해당 위치를 출력하면 된다.

1인 곳만 체크하기 시작하고 각 경우에 표적지를 탐색하는 시간을 곱하면,
100,000 x 19 x 19가 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] grid, target;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		grid = new int[N][M];
		List<int[]> candidates = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			for (int j = 0; j < input.length(); j++) {
				grid[i][j] = input.charAt(j) - '0';
				if (grid[i][j] == 1) {
					candidates.add(new int[] { i, j });
				}
			}
		}
		makeTarget();
		for (int[] pos : candidates) {
			int i = pos[0], j = pos[1];
			if (check(i, j)) {
				System.out.println(i + " " + j);
				System.exit(0);
			}
		}

		System.out.println(-1);
		br.close();
	}

	static boolean check(int i, int j) {
		int[] scoreCount = new int[11];
		for (int dx = 0; dx < 19; dx++) {
			for (int dy = 0; dy < 19; dy++) {
				int x = i + dx - 9;
				int y = j + dy - 9;
				if (inGrid(x, y) && grid[x][y] == 1) {
					scoreCount[target[dx][dy]]++;
				}
			}
		}

		for (int score = 1; score <= 10; score++) {
			if (scoreCount[score] != 1)
				return false;
		}
		return true;
	}

	static boolean inGrid(int x, int y) {
		return 0 <= x && x < N && 0 <= y && y < M;
	}

	static boolean in_range(int x, int y) {
		return 0 <= x && x < 19 && 0 <= y && y < 19;
	}

	static void makeTarget() {
		int[] dx = new int[] { 0, 1, 0, -1 };
		int[] dy = new int[] { 1, 0, -1, 0 };
		target = new int[19][19];
		Queue<int[]> q = new LinkedList<>();
		for (int i = 0; i < 19; i++) {
			target[i][0] = 1;
			target[i][18] = 1;
			q.add(new int[] { i, 0 });
			q.add(new int[] { i, 18 });
		}
		for (int j = 1; j < 18; j++) {
			target[0][j] = 1;
			target[18][j] = 1;
			q.add(new int[] { 0, j });
			q.add(new int[] { 18, j });
		}
		while (!q.isEmpty()) {
			int[] val = q.poll();
			int x = val[0], y = val[1];
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (in_range(nx, ny) && target[nx][ny] == 0) {
					target[nx][ny] = target[x][y] + 1;
					q.add(new int[] { nx, ny });
				}
			}
		}
	}
}