[BOJ] 백준 18248 - 감시 피하기 풀이

1. 문제

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

18428번: 감시 피하기

 

2. 풀이

백준 골드 5의 브루트포스, 백 트래킹 문제이다. 생각보다 골드 문제라기보단 실버 2 ~ 1의 문제인 것 같고, 오히려 직전에 푼 마인크래프트가 더 어렵다고 느껴졌다...

이 문제를 풀 때 잡았던 핵심은 백 트래킹으로 빈 공간에 장애물을 설치한 후 선생님의 위치에서 상하좌우로 배열의 끝까지를 탐색하고 학생을 만나는지를 판단하는 것이다.

우선 주어진 입력을 변수와 배열에 셋팅한다. 이 때 map에 데이터를 셋팅할 때 선생님의 위치를 미리 객체로 저장해놓고 리스트에 넣어두었다. 그 후 obstacleBackTracking 함수를 시작한다.

(1) obstacleBackTracking 함수는 장애물을 놓는 함수이다.
백트래킹으로 빈 공간에 장애물을 하나씩 놓고 장애물을 다 놓았다면 (= obstacleBackTracking의 obstacleCnt가 0개라면) searchStart 함수를 실행한다.

(2) searchStart 함수는 장애물을 놓은 후 선생님이 있는 위치를 탐색하면서 isNotSeeCnt를 카운트를 하는 함수이다. 선생님의 위치를 저장한 리스트를 하나씩 꺼내오면서 rowSearch, colSearch를 실행 후 둘 다 true라면 isNotSeeCnt를 하나 증가시킨다. 이 두 함수가 true라는 의미는 "꺼낸 선생님이 모종의 이유로 학생을 보지 못했다"를 의미한다.

(3) rowSearch와 colSearch는 범위만 다를 뿐 동일한 로직으로 동작한다.
rowSearch는 선생의 위치에서 본인의 위치를 제외하고 위, 아래를 탐색하면서 학생을 만난다면 false를 리턴하고 위, 아래 양쪽 다 장애물을 만난다면 기본인 true를 리턴한다.
colSearch는 선생의 위치에서 본인의 위치를 제외하고 왼쪽, 오른쪽을 탐색하면서 학생을 만난다면 false를 리턴하고 위, 아래 양쪽 다 장애물을 만난다면 기본인 true를 리턴한다.

모든 선생님에 대해 탐색을 마쳤다면 searchStart 함수에서 isNotSeeCnt가 선생님의 수와 같은지를 판단한다. 같다는 의미는 모든 선생님이 학생을 보지 못했다는 의미이므로 "YES"를 출력 후 프로그램을 종료한다.

만약 장애물을 놓을 수 있는 모든 경우를 탐색해도 YES를 출력할 수 없다면 NO를 출력한다!!

 

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int N;
    static boolean[][] visited;
    static char [][] map;

    static class TeacherPoint {
        int x;  // row
        int y;  // column

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

    // 선생의 위치를 담을 리스트
    static List<TeacherPoint> teacherPointList = new ArrayList<>();
    static BufferedWriter bw;
    static BufferedReader br;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 선생님은 T, 학생은 S, 장애물은 O
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new boolean[N][N];

        // map에 정보 담기
        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] == 'T') {
                    teacherPointList.add(new TeacherPoint(i, j));
                }
            }
        }

        obstacleBackTracking(3);

        bw.write("NO");
        bw.flush();
        bw.close();
        br.close();
    }

    // 장애물을 놓는 함수
    // obstacleCnt : 남아있는 장애물 수
    private static void obstacleBackTracking(int obstacleCnt) throws Exception {
        if (obstacleCnt == 0) {
            searchStart();
        } else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && map[i][j] == 'X'){
                        visited[i][j] = true;
                        map[i][j] = 'O';

                        obstacleBackTracking(obstacleCnt - 1);

                        visited[i][j] = false;
                        map[i][j] = 'X';
                    }
                }
            }
        }
    }

    // 장애물을 놓은 후 선생이 있는 위치부터 탐색을 시작하는 함수
    private static void searchStart() throws Exception {
        int isNotSeeCnt = 0;   // 학생을 보지 못한 선생의 수
        for (int i = 0; i < teacherPointList.size(); i++) {
            TeacherPoint searchPoint = teacherPointList.get(i);

            // 선생의 양옆 위아래를 탐색했을 때 학생을 보지 못했다면 isNotSeeCnt를 하나 증가시켜줌
            if (rowSearch(searchPoint) && columnSearch(searchPoint)) {
                isNotSeeCnt += 1;
            }
        }

        // 모든 학생이 감시로부터 피한 것
        if (isNotSeeCnt == teacherPointList.size()) {
            bw.write("YES");
            bw.flush();
            bw.close();
            br.close();

            System.exit(0);
        }
    }

    // 선생의 위치에서 row를 탐색하는 함수 ( row를 탐색한다는건 열 값이 움직인다.)
    private static boolean rowSearch(TeacherPoint searchPoint) throws Exception {
        // 현재 선생님의 컬럼값 위치에서 0까지 탐색
        for (int j = searchPoint.y - 1; j >= 0; j--) {

            // 학생을 발견한다면
            if (map[searchPoint.x][j] == 'S') {
                return false;   // 학생을 발견했다.
            } else if (map[searchPoint.x][j] == 'O') { // 장애물을 발견 했다면
                break;
            }
        }

        // 현재 선생님의 컬럼값부터 N - 1 까지탐색
        for (int j = searchPoint.y + 1; j < N; j++) {

            // 학생을 발견한다면
            if (map[searchPoint.x][j] == 'S') {
                return false;  // 학생을 발견했다.
            } else if (map[searchPoint.x][j] == 'O') { // 장애물을 발견 했다면
                break;
            }
        }

        return true; // 학생을 발견하지 못햇다
    }

    // 선생의 위치에서 Column을 탐색하는 함수(
    private static boolean columnSearch(TeacherPoint searchPoint) throws Exception {

        // 0부터 현재 선생님의 컬럼값 이전까지 탐색
        for (int j = searchPoint.x - 1; j >= 0; j--) {

            // 학생을 발견한다면
            if (map[j][searchPoint.y] == 'S') {
                return false; // 학생을 발견하지 못햇다
            } else if (map[j][searchPoint.y] == 'O') { // 장애물을 발견 했다면
                break;
            }
        }

        // 0부터 현재 선생님의 컬럼값 이전까지 탐색
        for (int j = searchPoint.x + 1; j < N; j++) {

            // 학생을 발견한다면
            if (map[j][searchPoint.y] == 'S') {
                return false; // 학생을 발견하지 못햇다
            } else if (map[j][searchPoint.y] == 'O') { // 장애물을 발견 했다면
                break;
            }
        }

        return true; // 학생을 발견하지 못햇다
    }
}

4. 배운 점

1. 백트래킹은 계속 반복해서 풀어보자. (모든 알고리즘이 그렇지만, 특히 백트래킹이나 dfs, bfs 등의 재귀를 활용하는 알고리즘은 아직 딱 보고 판단하기에는 실력이 부족한 것 같다.)

2. 이와 비슷한 연구소 문제도 다시 풀어보자!!