[백준] 18428 감시 피하기 - DFS(깊이우선탐색) + 브루트포스(bruteforce) + 조합(Combination) JAVA

https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

코드설명

DFS(깊이우선탐색) + 브루트포스(bruteforce) + 조합(Combination) 를 활용하는 문제입니다.

 

 

1. dfs 함수
   1. 재귀적으로 가능한 모든 경우의 수를 확인하며, 세 개의 장애물을 놓을 위치를 결정합니다. 세 개의 장애물을 놓은 후에는 checkTeacherFindable 함수를 호출하여 선생님들이 학생을 찾을 수 있는지 여부를 확인합니다.
2. checkTeacherFindable 함수는 선생님들 각각에 대해 상, 하, 좌, 우 방향으로 감시 가능한지를 확인합니다. 하나라도 학생을 찾을 수 있는 경우 true를 반환합니다.
3. gotoWayAndFindStudent 함수는 특정 방향으로 이동하면서 학생을 찾을 수 있는지 여부를 확인합니다. 장애물('O')을 만나면 학생을 찾을 수 없는 것으로 판단하고 false를 반환합니다.
4. 만약 학생을 찾을 수 없을경우가 하나라도 존재하면 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;
	}
}