[백준] 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 teachers = new ArrayList(); 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, Listteachers) { 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= 0 && map[x][y]==0)y--; if(y >= 0 && map[x][y]==1)return true; x=pos[0]+1; y=pos[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; } }

결과 화면

from http://nato-blog.tistory.com/164 by ccl(S) rewrite - 2021-12-26 02:28:27