[BOJ] 18428 감시 피하기 - JAVA

1. 문제

18428번: 감시 피하기

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.

각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다. 또한 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정하자.

다음과 같이 3x3 크기의 복도의 정보가 주어진 상황을 확인해보자. 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다. 선생님이 존재하는 칸은 T, 학생이 존재하는 칸은 S, 장애물이 존재하는 칸은 O로 표시하였다. 아래 그림과 같이 (3,1)의 위치에는 선생님이 존재하며 (1,1), (2,1), (3,3)의 위치에는 학생이 존재한다. 그리고 (1,2), (2,2), (3,2)의 위치에는 장애물이 존재한다. 

 

첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력한다. 모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력한다.

---

2. 풀이

정적 변수

char[][] board	교실 상태
boolean ANSWER	모든 학생들이 감시에서 벗어났는지 저장
int N	교실 크기
ArrayList<int[]> teacher	선생님들 위치

 

Main

1.  값을 입력받으면서 선생님 위치는 따로 list에 저장해둔다.

2.  pick 메서드를 실행시킨다.

3.  ANSWER가 true라면 YES, false라면 NO를 출력한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   StringTokenizer st;
   board = new char[N][N];
   teacher = new ArrayList<>();
   for(int i=0;i<N;i++){
      st = new StringTokenizer(in.readLine());
      for(int j=0;j<N;j++){
         board[i][j] = st.nextToken().charAt(0);
         if(board[i][j]=='T') teacher.add(new int[]{i,j});
      }
   }

   pick(0,0,0);

   if(ANSWER) System.out.println("YES");
   else System.out.println("NO");
}

 

Pick

1.  만약 ANSWER가 이미 true라면 끝낸다.(기저조건1)

2.  cnt==3이라면 감시하는 학생 수를 체크하고 그 값을 ANSWER에 저장한 뒤 끝낸다. (기저조건2)

3.  직전 지점이 i,j이다. 따라서 세로는 i부터, 가로는 j+1부터 시작한다. 물론 다음 세로 줄을 탐색하기 시작하면 nj도 0부터 탐색해야 한다.

4.  board[ni][nj]가 빈 공간 'X'라면 장애물로 표시한 후 다음 장애물을 설치하도록 재귀호출한다.

5.  재귀호출에서 돌아오면 현 자리를 다시 빈 공간으로 표시한다.

private static void pick(int cnt, int i, int j){
   if(ANSWER) return;
   if(cnt==3){
      ANSWER = check();
      return;
   }

   int nj;
   for(int ni=i;ni<N;ni++){
      if(ni==i) nj = j+1;
      else nj = 0;
      for(;nj<N;nj++){
         if(board[ni][nj]=='X'){
            board[ni][nj]='O';
            pick(cnt+1, ni, nj);
            board[ni][nj] = 'X';
         }
      }
   }
}

 

Check

1.  선생님 하나씩 탐색한다.

2.  사방탐색으로 진행하되, 중간에 장애물을 만나거나 범위에 벗어나면 끝낸다.

3.  탐색하다가 학생을 만나면 바로 false를 반환한다.

4.  중간에 반환되지 않았다면 true를 리턴한다.

private static boolean check(){
   int[][] deltas = {{1,0},{0,1},{0,-1},{-1,0}};
   int ni,nj;
   for(int[] t:teacher){
      for(int[] d:deltas){
         ni = t[0];
         nj = t[1];
         while(true){
            ni += d[0];
            nj += d[1];
            if(ni<0 || ni>=N || nj<0 || nj>=N) break;
            if(board[ni][nj]=='S') return false;
            else if(board[ni][nj]=='O') break;
         }
      }
   }

   return true;
}

 

전체 코드

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

public class BOJ_18428_감시피하기 {
   static char[][] board;
   static boolean ANSWER;
   static int N;
   static ArrayList<int[]> teacher;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      StringTokenizer st;
      board = new char[N][N];
      teacher = new ArrayList<>();
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=0;j<N;j++){
            board[i][j] = st.nextToken().charAt(0);
            if(board[i][j]=='T') teacher.add(new int[]{i,j});
         }
      }

      pick(0,0,0);

      if(ANSWER) System.out.println("YES");
      else System.out.println("NO");
   }

   private static void pick(int cnt, int i, int j){
      if(ANSWER) return;
      if(cnt==3){
         ANSWER = check();
         return;
      }

      int nj;
      for(int ni=i;ni<N;ni++){
         if(ni==i) nj = j+1;
         else nj = 0;
         for(;nj<N;nj++){
            if(board[ni][nj]=='X'){
               board[ni][nj]='O';
               pick(cnt+1, ni, nj);
               board[ni][nj] = 'X';
            }
         }
      }
   }

   private static boolean check(){
      int[][] deltas = {{1,0},{0,1},{0,-1},{-1,0}};
      int ni,nj;
      for(int[] t:teacher){
         for(int[] d:deltas){
            ni = t[0];
            nj = t[1];
            while(true){
               ni += d[0];
               nj += d[1];
               if(ni<0 || ni>=N || nj<0 || nj>=N) break;
               if(board[ni][nj]=='S') return false;
               else if(board[ni][nj]=='O') break;
            }
         }
      }

      return true;
   }
}

---

3. 결과