백준 - 감시 피하기(18428) - Java - DFS+BFS

1. 문제

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

2. 풀이

참고 풀이
https://dding9code.tistory.com/53

 
DFS와 BFS를 병행해야하는 풀이였다.

1. DFS로 장애물 3개를 놓고
2. BFS로 선생님의 감시범위를 찾으며 감시범위 안에 S가 속해있는지 파악한다.

2-1. ✨핵심 Point

1. 시스템 종료
   System.exit(0);

2. 선생님의 감시구역을 확인하는 곳
4방향에 대하여 한 방향에서 O를 만나기 전 까지 쭉 체크한다.

for(int mx = 0; mx < 4; mx++){
    int goX = x + moveX[mx];
    int goY = y + moveY[mx];
    while(goX >= 0 && goY >= 0 && goX < N && goY < N){
        if(copyMap[goX][goY] != 'O'){
            check[goX][goY] = true; 
            goX += moveX[mx];
            goY += moveY[mx];
        } else{
            break;
        }
    }
}

3. 학생들이 감시구역에 걸렸는지 확인

public static boolean checkStudent(boolean visit[][]) {
	for(Node node : listS) {
		if(visit[node.x][node.y]) {
			return false;
		}
	}
	return true;
}

3. 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;
    static char map[][];
    static int[] moveX = {1, -1, 0, 0};
    static int[] moveY = {0, 0, 1, -1};
    static ArrayList<Node> listT = new ArrayList<>(); // 선생님 좌표
    static ArrayList<Node> listS = new ArrayList<>(); // 학생 좌표
    
    public static class Node{
        int x;
        int y;
        
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());        
        map = new char[N][N];
        
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                map[i][j] = st.nextToken().charAt(0);
                if(map[i][j] == 'S'){
                	listS.add(new Node(i, j));
                } else if(map[i][j] == 'T') {
                    listT.add(new Node(i, j));
                }
            }
        }
        
        dfs(0, 0, 0);
        System.out.println("NO");
    }
    
    public static void dfs(int x, int y, int count){
        if(count == 3){
            bfs();
            return;
        }
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == 'X'){
                    map[i][j] = 'O';
                    dfs(i, j, count + 1);
                    map[i][j] = 'X';
                }
            }
        }
    }
    
    public static void bfs(){
        boolean check[][] = new boolean[N][N]; // bfs때마다 check배열 돌려야하기때문에 여기서 선언해준다.
        char copyMap[][] = new char[N][N];
        
        // 1. 배열 복사
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                copyMap[i][j] = map[i][j];
            }
        }
        
        // 2. 선생님 좌표 Queue에 담기
        Queue<Node> q = new LinkedList<>();
        for(int i = 0; i < listT.size(); i++){
            q.add(listT.get(i));
        }
        
        while(!q.isEmpty()){
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            
            check[x][y] = true;
            
            for(int mx = 0; mx < 4; mx++){
                int goX = x + moveX[mx];
                int goY = y + moveY[mx];
                
                while(goX >= 0 && goY >= 0 && goX < N && goY < N){
                    if(copyMap[goX][goY] != 'O'){
                        /* 이렇게하면 각 자리에 있는 S가 아니라 T S T일때 겹치는 감시구역이면 S가 두번 차감되어 다른 S가 있어도 YES로 출력될 수 있다.
                        if(copyMap[goX][goY] == 'S')
                            stuCount--;
                        */
                        check[goX][goY] = true; 
                        goX += moveX[mx];
                        goY += moveY[mx];
                    } else{
                        break;
                    }
                }
            }
        }
        
        if(checkStudent(check)) {
        	System.out.println("YES");
        	System.exit(0);
        }
    }
    
    public static boolean checkStudent(boolean visit[][]) {
    	
    	for(Node node : listS) {
    		if(visit[node.x][node.y]) {
    			return false;
    		}
    	}
    	return true;
    }
}