[백준] 18428번: 감시 피하기

문제

[백준] 18428번: 감시 피하기

분석

격자에 학생과 선생님의 정보가 있을때, 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피할 수 있는지 여부를 구하는 문제이다.

N이 최대 6으로 매우 작기 때문에, 설치 가능한 경우를 모두 점검하여 판단해도 시간초과 되지 않는다.
설치하는 개수만 파라미터로 가지고 진행하더라도 시간초과는 나지 않지만, 중복된 경우를 없애기 위해 위치 정보도 파라미터로 넣고 진행했다. 0부터 N x N - 1 까지 증가하는 숫자를 하나두고, N으로 나눈 몫이 x,나머지가 y로 정하면 숫자 하나로 위치 정보를 가져갈 수 있다.
백트래킹이기 때문에 설치가 끝나고 복구하는 작업도 잊지 않아야한다.

N*N 격자에서 3개를 고르는 경우, 선생님마다 방향 당 최대 N칸 검사하는 경우를 고려하면
$O(_{N^2}C_3 \times (T \times N))$이 시간 복잡도이다.

코드

해결언어 : Java

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

public class Main {
	static int N;
	static char[][] grid;
	static List<int[]> teachers;
	static boolean found;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		grid = new char[N][N];
		teachers = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				grid[i][j] = st.nextToken().charAt(0);
				if (grid[i][j] == 'T')
					teachers.add(new int[] { i, j });
			}
		}
		setting(0, 0);
		System.out.println(found ? "YES" : "NO");
		br.close();
	}

	static void setting(int pos, int i) {
		if (found)
			return;
		if (i == 3) {
			if (isPossible())
				found = true;
			return;
		}
		for (int n = pos; n < N * N; n++) {
			int x = n / N;
			int y = n % N;
			if (grid[x][y] == 'X') {
				grid[x][y] = 'O';
				setting(n + 1, i + 1);
				grid[x][y] = 'X';
			}
		}
	}

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

	static boolean isPossible() {
		int[] dx = { 0, 1, 0, -1 };
		int[] dy = { 1, 0, -1, 0 };
		for (int[] pos : teachers) {
			int x = pos[0], y = pos[1];
			for (int i = 0; i < dx.length; i++) {
				int nx = x, ny = y;
				while (true) {
					nx = nx + dx[i];
					ny = ny + dy[i];
					if (!in_range(nx, ny) || grid[nx][ny] == 'O')
						break;
					if (grid[nx][ny] == 'S')
						return false;
				}
			}
		}
		return true;
	}

}