[백준] 18428 - 감시 피하기

[문제링크]

18428번: 감시 피하기

 

0. 모든 선생님의 시야(일직선)를 피하도록 장애물을 설치할 수 있는지 묻는 문제

• 맵의 크기가 최대 6*6으로 작고, 선생님의 수도 5 이하로 적으니 brute-force로 해결 가능하다

 

1. setWall 재귀를 3번 진행하며 가능한 모든 조합으로 벽을 설치한다

 

2. 3개의 벽이 설치됬다면, 모든 선생님 기준으로 4방향 검사, 학생이 보이는지 검사한다

• 학생의 수(최대 30)에 비해 선생의 수(최대 5)가 적기 때문

 

3. 단 한 선생님이라도 학생이 보인다면 실패이므로, 결과값을 &로 누적한다

• = 모든 선생님이 학생을 보지 못했을 때만, true를 반환한다

 

4. 단 한 조합이라도 학생이 보이지 않았다면 성공이니, 결과값을 |로 누적한다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[][]map = new int[N][N];
		List<int[]> teachers = new ArrayList<int[]>(); 
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j < N; j++) {
				map[i][j]=pint(st.nextToken().charAt(0));
				if(map[i][j]==2) {
					teachers.add(new int[] {i,j});
				}
			}
		}
		
		System.out.println(setWall(0, 0, map, teachers)? "YES":"NO");
		
		
	}
	
	static boolean setWall(int level, int cur, int[][]map, List<int[]>teachers) {
		if(level==3) {
			//set 3 wall, verify
			boolean safe = true;
			for(int[] teacher : teachers) {
				// every teacher can't find student == safe
				safe &= !findStudent(map, teacher);
			}
			return safe;
		}
		
		int N = map.length;
		boolean returnV = false;
		for(int idx = cur; idx<N*N; idx++) {
			if(map[idx/N][idx%N] == 0) {
				map[idx/N][idx%N]=3; // set wall
				returnV |= setWall(level+1, cur+1, map, teachers); // recursivly check
				map[idx/N][idx%N]=0; // remove wall
			}
		}
		
		return returnV;
	}
	
	static boolean findStudent(int[][]map, int[]pos) {
		int x=pos[0], y=pos[1]+1;
		while(y<map.length && map[x][y]==0)y++;
		if(y < map.length && map[x][y]==1)return true;
		
		y=pos[1]-1;
		while(y >= 0 && map[x][y]==0)y--;
		if(y >= 0 && map[x][y]==1)return true;
		
		x=pos[0]+1; y=pos[1];
		while(x<map.length && map[x][y]==0)x++;
		if(x < map.length && map[x][y]==1)return true;
		
		x=pos[0]-1;
		while(x >= 0 && map[x][y]==0)x--;
		if(x >= 0 && map[x][y]==1)return true;
		
		return false;
	}
	
	static int pint(Character s) {
		if('S' == s)return 1;
		else if('T' == s)return 2;
		else return 0;
	}
}

 

결과 화면