백준 18428번 <감시 피하기>

백준 알고리즘 18428번

https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

---

18428번

N*N 크기의 복도가 있다. 특정 위치에 선생님, 학생, 장애물이 위치할 수 있다. 

학생들이 수업시간에 몰래 빠져나왔기 때문에 선생님들의 감시를 피하고 싶다. 선생님은 상하좌우 방향으로 감시를 한다. 이때, 장애물이 있다면 그 너머는 볼 수 없다. 선생님들의 시력은 매우 좋아서 장애물로 막혀있지 않다면 모두 볼 수 있다.

장애물 3개를 설치하여 복도에 나와있는 학생들이 모두 선생님의 감시를 피할 수 있는지 구하여라.

 

입력으로 복도의 크기 N이 들어오고 그 다음 N개의 줄에 걸쳐 복도의 상태가 들어온다.

 

출력으로 모든 학생이 선생님의 감시를 피할 수 있도록 장애물 3개를 설치할 수 있다면 YES를, 그렇지 않다면 NO를 출력하면 된다.

---

문제 해결

복도의 크기인 N이 최대 6이어서 최대 36개의 칸에서 3개의 칸을 골라 장애물을 설치하면 되기 때문에 조합을 이용해 풀 수 있다. 장애물을 설치하는 칸을 선택할 때는 i와 j를 고르는 것이 어렵다고 생각해서 각 칸에 index를 부여하여 해당 index를 선택하는 방식으로 진행하였다. 예를 들어 복도의 크기가 N이라고 할 때는 아래와 같이 index를 부여하였고 해당 칸의 i좌표와 j좌표는 몫과 나머지를 이용해 풀 수 있다.

• 장애물의 위치 3개를 모두 골랐다면 obstacle() 함수를 호출하여 학생들이 감시를 피할 수 있는지 확인한다.
  • 그 전에 선택된 장애물의 위치가 장애물이 있을 수 있는 곳인지 먼저 확인한다. → 가지치기
  • 선생님들이 상하좌우로 볼 수 있는 곳까지 본다.
    • 이때, while문을 도는데 범위를 벗어나거나 장애물을 만난다면 while문을 빠져나온다.
    • 만약 학생을 보게 된다면 감시를 피하지 못한 것이기 때문에 더 이상 진행할 필요가 없다.  →  가지치기
  • 만약 선생님들의 감시를 모두 피한다면 answer 값을 true로 만들어서 더 이상 프로세스를 진행하지 않도록 한다.  → 가지치기

---

코드

package boj18428;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

/*
 * 장애물의 위치 3개를 조합으로 구한다.
 * 입력으로 들어온 origin을 복사한 후 해당 위치에 대해 장애물을 설치한다.
 * 델타 탐색을 응용하여 선생님이 감시를 시작한다.
 * 이때 while문을 도는데 범위를 벗어나거나 장애물을 만나면 while문을 빠져나온다.
 * 만약 학생을 만난다면, 선생님의 감시에 걸린 것이기 때문에 더 이상 함수를 진행할 필요가 없다.
 * 선생님의 감시를 모두 피했다면 answer를 true로 만들어서 다음 프로세스를 더 이상 진행하지 않도록 처리한다. 
 * */

public class Main {
	static boolean answer;
	static int N;
	static String[][] origin;
	static ArrayList<Tuple> teachers;
	static int[] number;
	static int[] di = { -1, 1, 0, 0 };
	static int[] dj = { 0, 0, -1, 1 };

	static class Tuple {
		int i, j;

		public Tuple(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}
	}

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

		N = Integer.parseInt(br.readLine());
		origin = new String[N][N];
		teachers = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			String[] inArr = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				origin[i][j] = inArr[j];
				if (origin[i][j].equals("T")) {
					teachers.add(new Tuple(i, j));
				}
			}
		}
		answer = false;
		number = new int[3];
		combi(0, 0);
		if (answer) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}

	public static void combi(int cnt, int idx) {
		if (answer) {
			return;
		}
		if (cnt == 3) {
			obstacle();
			return;
		}
		for (int i = idx; i < N * N; i++) {
			number[cnt] = i;
			combi(cnt + 1, idx + 1);
		}
	}

	public static void obstacle() {
		String[][] map = copy(origin);

		for (int i = 0; i < 3; i++) {
			int q = number[i] / N;
			int r = number[i] % N;
			if (map[q][r].equals("X")) {
				map[q][r] = "O";
			} else {
				return;
			}
		} // 장애물 설치

		for (int i = 0; i < teachers.size(); i++) {
			Tuple tp = teachers.get(i);
			for (int k = 0; k < 4; k++) {
				int ni = tp.i + di[k];
				int nj = tp.j + dj[k];
				while (true) {
					if (ni < 0 || nj < 0 || ni >= N || nj >= N || map[ni][nj].equals("O")) {
						break;
					}
					if (map[ni][nj].equals("S")) {
						return;
					}
					ni += di[k];
					nj += dj[k];
				}
			}
		}
		answer = true;
	}

	public static String[][] copy(String[][] origin) {
		String[][] copy = new String[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				copy[i][j] = origin[i][j];
			}
		}
		return copy;
	}
}

 

---

결과

 

---