[Java]BOJ 18428回避監視(ブルートフォス)

BOJ 18428 S 1の監視を避ける

ブルトフル、dfs

silver1

🔍 問題の説明

https://www.acmicpc.net/problem/18428
NxNサイズの廊下があります.廊下は1×1の大きさの格子に分かれており、特定の位置は先生、学生、障害物であってもよい.今、何人かの学生が授業中にこっそり廊下を抜け出して、廊下を抜け出した学生が先生に発見されないようにすることを目標にしています.
各先生は自分の位置で上、下、左、右の4つの方向に監視しています.しかし、廊下に障害物があると、先生は障害物の後ろに隠れている学生を見ることができません.また、先生は上、下、左、右の4つの方向に対して、どんなに遠くても障害物が詰まる前に学生が見ることができると仮定しています.
3×3サイズの廊下の情報が出ていることを確認します.本問題では,位置値を表す場合(行,列)の形式で表す.先生が存在する格子はTで,学生が存在する格子はSで,障害物が存在する格子はOである.下図に示すように、(3,1)の位置は先生(1,1)、(2,1)、(3,3)の位置に学生が存在する.また(1,2),(2,2),(3,2)の位置に障害物が存在する.

このとき(3,3)位置に存在する学生は障害物の後ろに隠れているため,監視を避けることができる.しかし(1,1)と(2,1)の位置に存在する生徒会は先生に発見される.
学生たちは廊下の空きスペースから障害物を設置する場所を選び、3つの障害物を正しく設置しなければならない.その結果、3つの障害物が設置され、すべての学生が監視されないようにすることができるかどうかを計算した.NxNサイズの廊下で学生と先生の位置情報を取得する場合は、3つの障害物を正しく設定し、すべての学生が先生の監視を避けることができるかどうかを印刷するプログラムを作成してください.
例えば、N=5の場合、先生と学生の位置情報が得られたと仮定する.

このとき,下図のように3つの障害物を設け,すべての生徒が先生の監視を避けることができる.

✔入力

最初の行は自然数Nを与える.(3≦N≦6)第2行においてN行にまたがって廊下の情報を与える.各行には、N個の要素がスペースで区切られています.もしこの位置に学生、S、先生、Tがいたら、何も存在しなければ、Xをあげます.
しかし、全先生の人数は5以下の自然数、全学生の人数は30以下の自然数で、いつも3つ以上のスペースがあります.

✔出力

最初の行に3つの障害物を正しく設定し、出力がすべての学生が監視されないようにすることができるかどうか.すべての生徒に監視をさけることができれば「YES」、そうでなければ「NO」を出力します.

💡 に答える

問題を具現する.

障害物の数を設定します.(comb)

選択座標に障害物

を設ける.

3個の障害物を立ててDFS探索を行い、先生が学生を見ることができるかどうかをチェックします.

再び障害物を除去する.

💬 ソースコード

package boj.브루트포스;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

/***
 * 
 * 
 * ✨ Algorithm ✨
 * @Problem : BOJ 18428 감시피하기
 * @Author : Daun JO
 * @Date : 2021. 9. 6. 
 *
 */
public class Main_BOJ_18428_S1_감시피하기 {
	
	static int N;
	static char map[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static class Node {
		int x,y;

		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
	static ArrayList<Node> teachers = new ArrayList<>();
	static ArrayList<Node> blanks = new ArrayList<>();
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		
		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') teachers.add(new Node(i,j));
				if(map[i][j]=='X') blanks.add(new Node(i,j));
			}
		}
		
		visited = new boolean[blanks.size()];
		comb(0,0); //장애물 3개 선택 (blanks에서 선택)
		System.out.println("NO");
	}

	
	private static void comb(int cnt, int start) {
		if(cnt==3) {

			// 장애물 놓은 뒤 감시 피할 수 있는지 확인
			if(dfs()) {
				System.out.println("YES");
				System.exit(0);
			}

			return;
		}
		
		
		for(int i = start; i < blanks.size() ; i++) {
			if(visited[i]) continue;
			visited[i] = true;
			Node n = blanks.get(i);
			map[n.x][n.y]= 'O'; 
			comb(cnt+1, i+1);
			map[n.x][n.y]= 'X';
			visited[i]= false;
		}
	}


	private static boolean dfs() {
		
		for(Node n : teachers) {
			int x = n.x;
			int y = n.y; //선생님 위치를 기준으로 학생 볼수 있다면 => 실패
			
			for(int i = 0 ; i < 4 ; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				while(isIn(nx,ny)) {
					if(map[nx][ny]=='S') return false; //학생 찾았다. 감시 피할수 없음
					if(map[nx][ny]=='O') break; //장애물
					
					
					nx+=dx[i];
					ny+=dy[i];
				
				}
			}
		}
		return true; //감시 피했다면 성공
	}


	private static boolean isIn(int nx, int ny) {
		if(nx>=0&&ny>=0&&nx<N&&ny<N) return true;
		return false;
	}

}

💯 採点結果

12716	104