[백준] 18428번. 감시 피하기(JAVA)

문제

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

---

풀이

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

public class Main {

    static String[][] arr;
    static ArrayList<Point> student = new ArrayList<>();
    static String answer = "NO";
    static ArrayList<Point> gap = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        arr = new String[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();
                if(arr[i][j].equals("S")){
                    student.add(new Point(i,j));
                }
                if(arr[i][j].equals("X")){
                    gap.add(new Point(i,j));
                }
            }
        }
        placeObstacles(0, 0, n);
        System.out.println(answer);
    }

    static class Point {
        int x, y;

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

    // 장애물 3개를 배치하는 함수
    static void placeObstacles(int count, int start, int n) {
        if (count == 3) {
            if (checkAllStudents(n)) {
                answer = "YES";
            }
            return;
        }

        for (int i = start; i < gap.size(); i++) {
            Point p = gap.get(i);
            arr[p.x][p.y] = "O";  // 장애물 설치
            placeObstacles(count + 1, i + 1, n);
            arr[p.x][p.y] = "X";  // 장애물 제거
            if(answer.equals("YES")) return;  // 정답 찾으면 즉시 종료
        }
    }

    // 학생들이 선생님 시야에 안 걸리는지 체크하는 함수
    static boolean checkAllStudents(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j].equals("T")) {
                    if (checkDirection(i, j, n)) return false;
                }
            }
        }
        return true;
    }

    // 특정 선생님 방향으로 학생이 있는지 체크
    static boolean checkDirection(int x, int y, int n) {
        // 왼쪽
        for (int i = y - 1; i >= 0; i--) {
            if (arr[x][i].equals("O")) break;
            if (arr[x][i].equals("S")) return true;
        }
        // 오른쪽
        for (int i = y + 1; i < n; i++) {
            if (arr[x][i].equals("O")) break;
            if (arr[x][i].equals("S")) return true;
        }
        // 위쪽
        for (int i = x - 1; i >= 0; i--) {
            if (arr[i][y].equals("O")) break;
            if (arr[i][y].equals("S")) return true;
        }
        // 아래쪽
        for (int i = x + 1; i < n; i++) {
            if (arr[i][y].equals("O")) break;
            if (arr[i][y].equals("S")) return true;
        }

        return false;
    }
}

 

 단순하게 구현을 하는 문제라고 생각했다.

 장애물을 하나씩 놓아가는 방식을 통해 3개를 모두 놓게 되면 학생이 걸리지 않는지 검사한다. 이 때 검사가 완료된다면 바로 정답을 반환한다.

 

 만약, 장애물의 위치에서부터 동서남북으로 방향 검사를 진행하여 선생님을 마주한다면 그때는 통과가 되지 못하는 로직이다.

 

기준을 잘 잡는 연습을 하는 것이 중요하다.

선생님을 기준으로 할 것인지, 학생을 기준으로 할 것인지.

재귀적으로 장애물을 놓게 할 수 있는지 등의 연습이 중요할 것 같다.