https://www.acmicpc.net/problem/18428
18428번: 감시 피하기
NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복
www.acmicpc.net
코드설명
DFS(깊이우선탐색) + 브루트포스(bruteforce) + 조합(Combination) 를 활용하는 문제입니다.
- dfs 함수
- 재귀적으로 가능한 모든 경우의 수를 확인하며, 세 개의 장애물을 놓을 위치를 결정합니다. 세 개의 장애물을 놓은 후에는 checkTeacherFindable 함수를 호출하여 선생님들이 학생을 찾을 수 있는지 여부를 확인합니다.
- checkTeacherFindable 함수는 선생님들 각각에 대해 상, 하, 좌, 우 방향으로 감시 가능한지를 확인합니다. 하나라도 학생을 찾을 수 있는 경우 true를 반환합니다.
- gotoWayAndFindStudent 함수는 특정 방향으로 이동하면서 학생을 찾을 수 있는지 여부를 확인합니다. 장애물('O')을 만나면 학생을 찾을 수 없는 것으로 판단하고 false를 반환합니다.
- 만약 학생을 찾을 수 없을경우가 하나라도 존재하면 answer를 1로 설정합니다.
문제에서 유의해야할점은, 학생이 모두 숨을 수 있는 경우를 찾아야합니다. 즉, 선생님이 학생을 찾을경우는 실패한 케이스입니다. (숨을 수 없는 경우가 아닙니다.)
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N, M; public static int[][] arr; public static int answer = 0; public static Node[] teacher; public static int[] dx = {-1,1,0,0}; public static int[] dy = {0,0,-1,1}; public static int teacherCnt = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); arr = new int[N][N]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { arr[i][j] = st.nextToken().charAt(0) - 'A'; if(arr[i][j] == 'T' - 'A') { teacherCnt += 1; } } } int idx = 0; teacher = new Node[teacherCnt]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if(arr[i][j] == 'T' - 'A'){ teacher[idx++] = new Node(i, j); } } } dfs(0,0,0); if(answer == 1) System.out.println("YES"); else System.out.println("NO"); } public static void dfs(int level, int r, int c) { if( c >= N) { r = r + 1; c = 0; } if(level == 3) { // System.out.println("===================="); // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // System.out.print(" "+(char) (arr[i][j] + 'A')); // } // System.out.println(); // } if(checkTeacherFindable() == false) { //만약 찾을수 없을경우, answer = 1; } return ; } if(r >= N) return ; if(arr[r][c] == 'X' - 'A') { int before = arr[r][c]; arr[r][c] = 'O' - 'A'; dfs(level + 1, r, c + 1); arr[r][c] = before; } dfs(level, r, c + 1); } public static boolean checkTeacherFindable() { // for(int i=0;i<teacher.length;i++) { for(int dir = 0; dir < 4; dir++ ) { if(gotoWayAndFindStudent(teacher[i].r, teacher[i].c, dir) == true) { //만약 찾는다면 true, 아니라면 false. return true; } } } return false; } public static boolean gotoWayAndFindStudent(int r, int c, int dir) { if(arr[r][c] == 'S' - 'A') { //만약 학생을 찾는다면 return true. return true; } if(arr[r][c] == 'O' - 'A') { //만약 장애물을 발견한다면 못찾는것입니다. return false; } // System.out.println("R:"+r+"C:"+c+"dir:"+dir); int nr = r + dx[dir]; int nc = c + dy[dir]; if(nr < 0 || nr >= N || nc < 0 || nc >= N) return false; //만약 범위를 벗어난다면 못찾는것입니다. return gotoWayAndFindStudent(nr, nc, dir); } } class Node{ int r; int c; public Node(int r, int c) { this.r=r; this.c=c; } }