백준 18428 - 감시 피하기

Java

18428 번 - 감시 피하기

문제

접근 방법

DFS의 조합을 사용하여 3개의 장애물을 설치하기 위한 정수 3개를 뽑는다. (0 <= k < n * n)

뽑은 정수를 좌표로 변환한다.

y = 뽑은 정수 / n
x = 뽑은 정수 % n

이후 임시 테이블에 뽑은 장애물을 설치한 뒤,
각 선생의 상,하,좌,우를 탐색하여 학생이 나오지 않는지 확인한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result, N;
	static int[] sel;
	static char[][] map, temp;
	static List<int[]> teacher;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	N = (int)Math.pow(n, 2);
    	sel = new int[3];

    	map = new char[n][n];
    	teacher = new ArrayList<>();
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stk.nextToken().charAt(0);

    			if(map[i][j] == 'T') {
    				teacher.add(new int[] {i, j});
    			}
    		}
    	}

    	DFS(0, 0);
    	if(result == 1) {
    		System.out.println("YES");
    	}
    	else {
    		System.out.println("NO");
    	}

    	br.close();
	}

	static void DFS(int lv, int st) {
		if(lv == 3) {
			temp = new char[n][n];
			for(int i = 0; i < n; i++) {
				temp[i] = map[i].clone();
			}
			if(cal()) {
				result = 1;
			}
			return;
		}

		for(int i = st; i < N; i++) {
			sel[lv] = i;
			DFS(lv + 1, i + 1);
		}

	}
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};

	private static boolean cal() {
		int curN, y, x, ny, nx;
		// 장애물 설치
		for(int i = 0; i < 3; i++) {
			curN = sel[i];
			y = curN / n;
			x = curN % n;
			// 선생 or 학생 위로 장애물이 설치 될 수 없다.
			if(temp[y][x] != 'X')
				return false;
			temp[y][x] = 'O';
		}


		// 선생의 탐색
		for(int[] yx : teacher) {
			y = yx[0];
			x = yx[1];

			for(int i = 0; i < 4; i++) {
				ny = y;
				nx = x;

				// 범위가 벗어날 때 까지 탐색
				while(isIn(ny, nx)) {
					if(temp[ny][nx] == 'O') {
						break;
					}
					else if(temp[ny][nx] == 'S') {
						return false;
					}

					ny += dy[i];
					nx += dx[i];
				}
			}
		}

		return true;
	}

	 // 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점