[백준 18428] 감시 피하기 in JAVA

www.acmicpc.net/problem/18428

18428번: 감시 피하기

※ 풀이 방법

 먼저 아무것도 없는 위치 중 세 곳을 골라 장애물을 설치해주었다 -> 백트래킹

 장애물이 설치된 곳이 세 곳이 되면 학생들이 감시를 피할 수 있는지 체크해주었다.

 각 케이스별로 체크해서 학생들이 감시를 피할 수 있는 케이스가 하나라도 있다면 YES 출력, 하나도 없으면 NO를 출력했다.

 원래는 학생들의 위치를 따로 저장하려고 했으나 학생은 최대 30명, 선생님은 최대 5명 있기 때문에 선생님의 위치를 따로 저장했다.

 

※ 문제 풀이 코드

import java.util.Scanner;

public class BOJ_18428 {
	public static String [][] arr;
	public static int ans=0;
	public static int [][] T;
	public static int t;
	
	public static void ck(int N) {
		int x,y,cnt=0;//학생이 걸린 횟수
		for(int i=0;i<t;i++) {
			x=T[i][0];
			y=T[i][1];
			for(int j=x-1;j>=0;j--) {//상
				if(arr[j][y].equals("S")) cnt++;
				if(arr[j][y].equals("O")) break;
			}
			for(int j=x+1;j<N;j++) {//하
				if(arr[j][y].equals("S")) cnt++;
				if(arr[j][y].equals("O")) break;
			}
			for(int j=y-1;j>=0;j--) {//좌
				if(arr[x][j].equals("S")) cnt++;
				if(arr[x][j].equals("O")) break;
			}
			for(int j=y+1;j<N;j++) {//우
				if(arr[x][j].equals("S")) cnt++;
				if(arr[x][j].equals("O")) break;
			}
		}
		
		if(cnt==0) ans++;
	}
	
	public static void bt(int n,int r,int c,int N) {
		if(r>=N||c>=N) return;//범위 벗어났을 경우
		
		if(n==3) {//장애물 3개 모두 설치했을 경우
			ck(N);//학생이 걸리는지 체크
			return;
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(arr[i][j].equals("X")) {//arr[i][j]가 빈자리라면(학생 x, 선생 x, 장애물 x)
					arr[i][j]="O";//장애물 설치
					bt(n+1,i,j,N);//다음 위치 확인
					arr[i][j]="X";//장애물 해제
				}
			}
		}
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
		
		int N=input.nextInt();
		
		arr=new String[10][10];
		T=new int[10][2];
		t=0;
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				arr[i][j]=input.next();
				if(arr[i][j].equals("T")) {//선생님 위치 저장
					T[t][0]=i;
					T[t][1]=j;
					t++;
				}
			}
		}
		
		bt(0,0,0,N);
		
		//학생이 안 걸린 경우가 한 번이라도 있으면 YES 출력, 그렇지 않으면 NO 출력
		if(ans==0) System.out.println("NO");
		else System.out.println("YES");
	}

}