[백준][Java] 18428번 : 감시 피하기

[문제 링크]

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

---

문제 설명

T-선생님, S-학생, O-장애물, X-아무것도 존재하지 않음

복도에 학생들이 선생님의 감시에 들키지 않도록 장애물을 설치한다.

- 선생님은 본인의 위치에서 상하좌우로 감시 가능

- 선생님과 학생 사이에 장애물이 있으면 학생을 볼 수 없음

3개의 장애물을 설치해서 모든 학생이 선생님의 감시로부터 피할 수 있는지를 구한다.
모두 피할 수 있으면 YES, 그렇지 않으면 NO

 

 

 

 

 

 

 

문제 풀이

• 복도의 정보를 입력받으면서 T(선생님)의 위치 정보를 teachers 리스트에 따로 저장한다.
• dfs 탐색으로 장애물 3개를 세우는 모든 경우의 수를 구한다.
• 벽이 3개가가 된 경우, bfs 탐색으로 현재 상태에서 모든 학생이 감시를 피할 수 있는지 확인한다.
  • teachers 에서 선생님의 위치를 하나씩 꺼내서 상하좌우에 학생 or 장애물이 발견되는지 탐색한다. 
  • S(학생)이 발견되는 경우 : 감시를  피할 수 없다 → false
  • O(장애물)이 발견되는 경우 : 감시를 피할 수 있다 → true
  • true이면 cnt 증가
  • 이렇게 모든 선생님의 위치에서 탐색한 후, cnt의 값이 선생님의 수와 일치하면 "YES", 그렇지 않으면 "NO"

 

전체 코드

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

class Position {
    int x;
    int y;

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


public class Main {

    static int n;
    static String[][] map;
    static ArrayList<Position> teachers = new ArrayList<>();
    static String result = "NO";

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        map = new String[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = st.nextToken();
                //선생님의 위치 정보 저장
                if (map[i][j].equals("T")) {
                    teachers.add(new Position(i, j));
                }
            }

        }
        dfs(0);
        System.out.println(result);
    }

    public static void dfs (int walls){
        //종료조건
        if (walls == 3) {
            //모든 학생이 감시를 피할 수 있는지 확인
            findStudents();
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j].equals("X")) {
                    map[i][j] = "O";
                    dfs(walls + 1);
                    map[i][j] = "X";
                }
            }
        }
    }

    public static void findStudents() {
        int cnt = 0;
        for (Position teacher : teachers) {
            if (find(teacher)) {
                cnt++;
            }
        }
        //모든 선생님이 학생을 발견하지 못했다면 YES
        if (cnt == teachers.size()) {
            result = "YES";
        }
    }


    public static boolean find (Position teacher) {
        int x = teacher.x;
        int y = teacher.y;

        //상
        for (int i = x; i >= 0; i--) {
            if (map[i][y].equals("S"))  return false;   //학생 발견-> 감시를 피하지 못함

            if (map[i][y].equals("O"))  break;  //장애물 발견-> 감시를 피할 수 있음
        }

        //하
        for (int i = x; i < n; i++) {
            if (map[i][y].equals("S"))  return false;

            if (map[i][y].equals("O"))  break;
        }

        //좌
        for (int i = y; i >= 0; i--) {
            if (map[x][i].equals("S"))  return false;

            if (map[x][i].equals("O"))  break;
        }

        //우
        for (int i = y; i < n; i++) {
            if (map[x][i].equals("S")) return false;

            if (map[x][i].equals("O")) break;
        }
        return true;
    }
}

 

 

 

 

 

나의 풀이(실패한 풀이)

처음에 나는 위와 반대로 학생을 기준으로 해서 학생의 상하좌우에 1. 선생님이 없거나 2. 장애물이 있는 경우, 감시를 피할 수 있다고 생각하고 문제를 풀었다.(갑자기 왜 학생을 기준으로 하자고 생각했는진 모르겠지만..😅)

학생의 위치 students 리스트와 선생님의 위치 teachers 리스트를 따로 생성하고,

한 명의 학생을 기준으로 해서 teachers를 돌면서 학생의 상하좌우에 선생님이 있는지 확인한다.

• 학생의 x좌표 = 선생님의 x좌표 → 학생의 좌우에 선생님이 존재한다.
• 학생의 y좌표 = 선생님의 y좌표 → 학생의 상하에 선생님이 존재한다.
• 위의 두 경우 중 하나가 만족할 때, 학생과 선생님 사이에 장애물이 있으면 감시를 피할수 있고(true), 그렇지 않으면 피할 수 없다.(false)
• 위의 두 경우를 모두 만족하지 못하면, 다음 선생님으로 넘어간다.

풀이가 조금 복잡하긴 하지만 예제 2개를 실행했을 때 결과는 맞게 나왔었는데 왜 실패했는지 아직도 잘 모르겠다...

//모든 학생이 감시로부터 피할 수 있는지 체크하는 메서드
public static boolean check(int x, int y) {
    //학생위치의 상하좌우에 선생님이 존재하는지 확인
    for (int i = 0; i < teachers.size(); i++) {
        int x_teacher = teachers.get(i).x;
        int y_teacher = teachers.get(i).y;

        //학생의 x좌표와 선생님의 x좌표가 같은 경우 -> 학생의 좌우에 선생님 존재
        if (x == x_teacher) {
            if (x_teacher < x) {    //학생의 왼쪽에 선생님 존재
                for (int j = y_teacher; j < y; j++) {	//학생과 선생님 사이에 장애물이 존재하는지 확인
                    return (map[x][j].equals("O") ? true : false);
                }
            } else {    //학생의 오른쪽에 선생님 존재
                for (int j = n - 1; j > y; j--) {
                    return (map[x][j].equals("O") ? true : false);
                }
            }
        }


        //학생의 y좌표와 선생님의 y좌표가 같은 경우 -> 학생의 상하에 선생님 존재
        if (y == y_teacher) {
            if (y_teacher < y) {    //학생의 위에 선생님 존재
                for (int j = x_teacher; j < x; j++) {	//학생과 선생님 사이에 장애물이 존재하는지 확인
                    return (map[j][y].equals("O") ? true : false);
                }
            } else {    //학생의 아래에 선생님 존재
                for (int j = n - 1; j > x; j--) {
                    return (map[j][y].equals("O") ? true : false);
                }
            }
        }
    }
    return false;
}