[BOJ 18428] 감시피하기

문제

• BOJ 18428
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1.빈칸을 기준으로 장애물 3개를 구하는 함수 comb()를 만든다.

1. 1에서 3개의 좌표를 구했으면, 이 좌표를 기준으로 전체 선생님 좌표를 돌면서 그래프를 탐색한다.
   2-1. 탐색을 하면서 다음 좌표가 범위 안에 있고, 학생인 경우에는 더이상 이 경우를 돌 필요가 없으므로 빠져나온다.
   2-2. 장애물을 만난 경우 더이상 앞으로 갈 수 없으므로 다음 방향을 바라보고 탐색한다.
   2-3. 빈칸인 경우 계속 앞으로 갈 수 있으므로 현재 방향으로 계속해서 탐색한다.
2. 만약 2에서 끝까지 탐색을 완료했다면 학생을 한번도 만나지 않았으므로 이 경우에 모든 학생이 선생님의 감시를 피할 수 있다. 따라서 “YES”를 출력하고 프로그램을 종료한다. System.exit(0);
3. 만약 2에서 끝까지 탐색을 완료했다면 학생을 한번도 만나지 않았으므로 이 경우에 모든 학생이 선생님의 감시를 피할 수 있다. 따라서 “YES”를 출력하고 프로그램을 종료한다. System.exit(0);
4. 만약 모든 경우를 탐색했는데 끝까지 3번의 경우가 나오지 않았다면 마지막에 “NO”를 출력한다.

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

class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static char[][] map;
	static boolean[] visited;
	static List<Point> teacherList, blankList;
	static int N;
	static int[][] dArr = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];

		teacherList = new ArrayList<>();
		blankList = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = st.nextToken().charAt(0);

				if (map[i][j] == 'T') teacherList.add(new Point(i, j)); //선생님
				else if(map[i][j] == 'X') blankList.add(new Point(i, j)); //빈칸
			}
		} // End input

		selected = new int[3];
		visited = new boolean[blankList.size()];
		// 1. 장애물 리스트에서 3개 뽑기
		comb(0, 0);

		System.out.println("NO");
	}

	static int[] selected;

	private static void comb(int cur, int cnt) {
		if (cnt == 3) {
			//2. 모든 선생님 돌면서 감시 피할수 있는지 체크
			if(dfs()) {
				System.out.println("YES");
				System.exit(0);
			}
			return;
		}

		for (int i = cur; i < blankList.size(); i++) {
			if(!visited[i]) {
				visited[i] = true;
				Point p = blankList.get(i);
				map[p.x][p.y] = 'O'; //장애물 설치
				comb(i + 1, cnt + 1);
				map[p.x][p.y] = 'X'; //원복
				visited[i] = false;
			}
		}
	}

	private static boolean dfs() {
		//선생님 탐색
		for(Point p : teacherList) {
			for(int d=0; d<4; d++) {
				int nx = p.x + dArr[d][0];
				int ny = p.y + dArr[d][1];
				
				while(true) {
					if(nx >= 0 && nx<N && ny>=0 && ny<N) {
						if(map[nx][ny] == 'S') return false; //학생 찾음
						else if(map[nx][ny] == 'O') break; //장애물->다음 방향 탐색
						
						//다음 좌표 탐색
						nx += dArr[d][0];
						ny += dArr[d][1];
					}else break;
				}
			}
		}
		
		//끝까지 학생 못찾았으면 감시피하기 성공
		return true;
	}
}