[JAVA] 백준 18428 - 감시피하기

 

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

 

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

public class Main {

    static int N;
    static String[][] map;
    static boolean[][] visited;
    static ArrayList<Point> teacherList = new ArrayList<>();
    static ArrayList<Point> list = new ArrayList<>();
    static int c;
    static boolean ans = false;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new String[N][N];
        visited = new boolean[N][N];
        for(int i = 0 ; i < N ; i++){
            String[] lines = br.readLine().split(" ");
            for(int j = 0 ; j < N ; j++){
                map[i][j] = lines[j];
                if(map[i][j].equals("T")) teacherList.add(new Point(i,j));
               list.add(new Point(i,j));
            }
        }
        dfs(0,0);
        if(ans) {
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }

    static void dfs(int depth, int count){
        if(count == 3){
            check();
            return;
        }

        for(int i = depth ; i < N * N ; i++){
            Point cur = list.get(i);
            if(map[cur.x][cur.y].equals("X")) {
                map[cur.x][cur.y] = "O";
                dfs(i + 1, count + 1);
                map[cur.x][cur.y] = "X";
            }
        }
    }
    static void check(){

        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        boolean yes = true;
        for(Point p : teacherList){
            for(int i = 0 ; i <4 ; i++){
                int x = p.x + dx[i];
                int y = p.y + dy[i];
                int step = 0;
                while(step <= N){
                    step++;
                    if(x < 0 || x >= N || y < 0 || y >= N || map[x][y].equals("O")){
                        break;
                    }
                    if (map[x][y].equals("S")) {
                        yes = false;
                        break;
                    }
                    x += dx[i];
                    y += dy[i];
                }
            }
        }
        if(yes){
            ans = yes;
        }

    }

}

class Point{
    int x;
    int y;

    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    
}

 

 

깨달은 점 : 2차원 (x,y)형태의 조합 브루트포스는 이중 for문을 쓰지말고, 1중 포문을 쓰되 N * N으로 하면 해결가능하다.