백준 18428번: 감시 피하기 (Java)

접근

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

18428번: 감시 피하기

단순한 dfs 문제였습니다. X가 표시된 위치 중 3군데를 선택하여 장애물을 놓고, 선생님의 위치에서 4방향으로 탐색하여 학생을 만나는지를 체크해주기로 합니다.

추가적으로 시간을 아끼기 위해 모든 X 위치에 장애물을 놓지 않고, 장애물을 놓았을 때 적어도 선생님의 시야를 막는 위치를 장애물의 후보군으로 놓기로 하였습니다. 이 위치는 탐색 전에 선생님의 위치에서 네방향으로 뻗어나가면서, 지도 바깥으로 나가거나 장애물을 만나기 전까지 모든 빈 공간을 ArrayList로 저장해줌으로써 미리 확인할 수 있습니다.

이렇게 구해진 장애물 위치의 후보들을 dfs 알고리즘을 통해 선택하면서 장애물로 바꾸고, 3개가 선택이 완료되면 선생님의 위치로부터 학생이 보이는지 확인하는 check함수를 구성하여 문제를 해결하였습니다.

한가지 주의할 점은, 문제에서는 선생님의 수가 5 이하의 자연수라고 주어지지만, 백준의 테스트케이스에는 선생님이 5명 이상인 케이스가 들어가있는 것 같다. 선생님의 수를 5로 미리 초기화하였더니 array index out of bound 에러가 발생하여 ArrayList를 이용하여 선생님의 수를 추가할 수 있게 만들었더니 통과하였다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static class Node {

    private int r, c;

    public Node(int r, int c) {
      this.r = r;
      this.c = c;
    }

    @Override
    public boolean equals(Object object) {
      Node o = (Node) object;
      if (this.r == o.r && this.c == o.c) {
        return true;
      } else {
        return false;
      }
    }
  }

  static int N;
  static boolean ans;
  static char[][] map;
  static ArrayList<Node> teacher = new ArrayList<>();
  static ArrayList<Node> position = new ArrayList<>();
  static int[] dr = { 0, 1, 0, -1 };
  static int[] dc = { 1, 0, -1, 0 };

  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] == 'T') teacher.add(new Node(i, j));
      }
    }
    br.close();
    setPosition();
    dfs(3, -1);
    if (ans) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }

  // 선생님의 시야 안에 있는 위치를 장애물 위치 후보군으로 저장
  static void setPosition() {
    for (int t = 0; t < teacher.size(); t++) {
      Node tmp_teacher = teacher.get(t);
      for (int i = 0; i < 4; i++) {
        for (int j = 1; j < N; j++) {
          int nr = tmp_teacher.r + dr[i] * j;
          int nc = tmp_teacher.c + dc[i] * j;
          if (mapOut(nr, nc) || map[nr][nc] == 'O') break;
          if (map[nr][nc] != 'X') continue;
          if (!position.contains(new Node(nr, nc))) position.add(new Node(nr, nc));
        }
      }
    }
  }

  static boolean mapOut(int r, int c) {
    return (r < 0 || N <= r || c < 0 || N <= c);
  }

  // 현재 선생님의 위치에서 학생이 보일 경우, false 리턴
  static boolean check() {
    for (int t = 0; t < teacher.size(); t++) {
      Node tmp_teacher = teacher.get(t);
      for (int i = 0; i < 4; i++) {
        for (int j = 1; j < N; j++) {
          int nr = tmp_teacher.r + dr[i] * j;
          int nc = tmp_teacher.c + dc[i] * j;
          if (mapOut(nr, nc) || map[nr][nc] == 'O') break;
          if (map[nr][nc] == 'S') return false;
        }
      }
    }
    return true;
  }

  // 장애물을 놓고, 장애물이 3개 전부 위치되었을 경우 학생이 선생님으로부터 무사한지 체크하는 dfs 함수
  static void dfs(int depth, int last) {
    // 이미 정답이 있음이 확인되었다면 탐색을 종료
    if (ans == true) return;
    // 장애물을 3개 다 놓았을 경우, check 하여 학생이 무사할 경우 ans = true
    if (depth == 0) {
      if (check()) ans = true;
      return;
    }
    for (int i = last + 1; i <= position.size() - depth; i++) {
      Node np = position.get(i);
      map[np.r][np.c] = 'O';
      dfs(depth - 1, i);
      map[np.r][np.c] = 'X';
    }
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!