백준 18428 (감시 피하기) - java

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

18428번: 감시 피하기

중요 구현 관점 !!

 1. 선생의 위치를 기준으로 상하좌우 모든 칸들을 파악할 수 있도록 함수를 설계 가능한가 ?

 2. 백트랙킹 문제를 풀때 가장 중요한 travel(재귀 함수) 구현 시 호출 값(증감 값) / 탈출 조건 / 상태 조건

 

 호출 값 : 위 문제에서는 벽을 최대 3개 까지 설치 할 수 있으니 호출 값은 벽의 개수 !

 탈출 조건 : 벽을 3개 설치 했을 때 선생의 감시를 모두 피할 수 있는지 판단하고 함수를 return해줘야 한다.

 상태 조건 : 좌표계를 기준으로 해당 좌표에 설치 , 비 설치

 

분명히 전체 선생님의 수는 5 이하의 자연수라고 입력에 써져 있는데 이상하게 선생님을 담을 배열(말이 좀 그렇네 ㅋ)의 크기가 9 미만이면 Indexout 에러가 발생한다. 문제가 잘못된건가 ? 혹시 그 이유를 아시는 분이 계시다면 댓글 부탁드립니다 ^.^

 

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

public class Main {
    static String result = "NO";
    static int n = 0;
    static StringTokenizer st;
    static int[][] board = new int[8][8]; // 좌표계
    static boolean[][] isIt = new boolean[8][8]; // 방문 (상태) 여부
    static point[] teacher = new point[9]; // !!!!! 문제의 선생님을 담는 배열 !!!!!
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0}; // 각각 상하좌우 이동 
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=n;j++)
            {
                String s = st.nextToken();
                if(s.equals("X"))
                    board[i][j] = 0;
                else if(s.equals("T")) {
                    board[i][j] = 2;
                    teacher[count++] = new point(i,j);
                }
                else
                    board[i][j] = 1;
            }
        }

        travel(0,1,1);
        System.out.println(result);
        br.close();
    }
    static boolean search1(point cur,int pos) // 해당 좌표를 기준 (선생님)으로 탐색 , pos값은 상하좌우 구분용
    {
        int nx = cur.x;
        int ny = cur.y;
        while(true)
        {
            nx = nx+dx[pos];
            ny = ny+dy[pos];

            if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
            {
                if(board[nx][ny]==3)
                {
                    return false; // 벽은 3이다 .... 벽일 경우 해당 시야에서 탐색 종료 
                }
                else if(board[nx][ny]==1)
                {
                    return true; // 1은 학생 , 찾으면 true
                }
            }
            else
            {
                return false; // 모든 좌표를 탐색했지만 찾지 못한 경우
            }
        }
    }
    static void travel(int k,int i,int j)
    {
        if(j>n)
        {
            i=i+1;
            j=1;
        } // 해당 열이 끝이므로 다음 행으로 상태 이동
        if(i>n)
        {
            return;
        } // 탐색 종료 
        if(k==3) // 벽을 3개 전부 설치한 경우 
        {
            for(int s=0;s<count;s++) // 모든 선생님에 대하여
            {
                if(!search1(teacher[s],0)&&!search1(teacher[s],1)&&!search1(teacher[s],2)&&!search1(teacher[s],3))
                {
                    continue;
                } // 학생을 찾지 못한 경우
                else{
                    return;
                } // 학생을 찾은 경우 바로 반환
            }
            result = "YES"; // 모든 선생님이 학생을 찾지 못한 경우이기 때문에 결과값을 YES로
            return;
        }

        if(!isIt[i][j]&&board[i][j]==0) // 벽을 칠수 있는 공간(빈공간 = 0)인가? 그리고 상태 여부 판단
        {
             isIt[i][j]=true;
             board[i][j] = 3;
             travel(k+1,i,j+1);
             isIt[i][j]=false;
             board[i][j] = 0;
        }
        travel(k,i,j+1); // 위 조건이 아닌 경우 다음 좌표로 이동 
    }
    }
class point
{
    int x;
    int y;
    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }

}