백준 18428 감시 피하기

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

백트래킹 실버1

나름 엄청 어렵게 접근했는데 이게 왜 실버1인지 고민을 한문제였다..

그리고 실수를많이해 남의 풀이를 많이찾아보았다..

내가생각한거는 다음과 같다.

벽을 배치할때 검사를 하는것이다. 이벽이 유효한 배치인가 ?

벽을 배치할때도 상하좌우 검사를 한후에 상하좌우에 선생이랑 학생이 둘다없다면 굳이 배치할 이유가없다라는 결과가나온다..
그렇게 horizon 과 vertical 검사를 한후에..

배치 유무에 따라 다음 넘어가는 재귀를 2개 태우고 다음칸으로 이동하면 되는느낌이엿는데..

학생수가 3명이 고정인줄알고 고정배열 하는실수와 배치할때 상하좌우로 퍼지는 식으로 접근했다는점과

그렇게 접근했을때 visited 체크를 따로 안해줫다는점..
이런 여러요인이 모여서 stack overflow도되고... 막문제가많았다..

그리고 풀이를 보니 되게간단했따..

고려해야할 부분이 적어서 실버1인가보다 ㅇㅇ

메인 로직

1. N * N 칸에 3개의 말 배치 (Nc3) 이므로 왠만하면 다된다 ㅇㅇ
2. 배치후 검사하기
3. 끝

visited 체크를 따로 안했는데 어차피 1,5,7 두나 7,5,1 두나 똑같기때문에 visited 체크를 해주었다면 좀더 더나은성능이 나올수있을것이라고 생각.. 근데.. 안해도..통과가됨..

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

public class 감시피하기 {

	static int N;
	static int[][] array; 
	static boolean[][] visited;
	static int[] sx; 
	static int[] sy;
	static boolean flag;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int sindex= 0;
		visited = new boolean[N][N];
		array = new int[N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				String cur = st.nextToken();
				int type = 3;
				if(cur.equals("X")) type =3; //방어막 가능 공간
				else if(cur.equals("S")) {
					type = 0; //학생
					sindex++; //학생인원수 카운팅
					visited[i][j] = true;
				}
				else {
					type = 1; //선생
					visited[i][j] = true;
				}
				array[i][j] = type;
			}
		}
        // 학생의 위치를 배열로넣어주기
		sx = new int[sindex];
		sy = new int[sindex];
		sindex=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(array[i][j]==0) {
					sx[sindex] = i;
					sy[sindex] = j;
					sindex++;
				}
			}
		}

		flag =false;
		start(0);
		if(flag) System.out.println("YES");
		else System.out.println("NO");

	}
	
	public static void start(int c) {
		if(c==3) {

			for(int i=0;i<sx.length;i++) {
				int curx = sx[i];
				int cury = sy[i];
				
				//상 검색
				
				for(int j=curx+1;j<N;j++) {
					if(array[j][cury]==2) break;
					if(array[j][cury]==1) {
						return;
					}
				}
				
				//하 검색
				
				for(int j=curx-1;j>=0;j--) {
					if(array[j][cury]==2) break;
					if(array[j][cury]==1) {
						return;
					}
				}
				
				//우 검색
				
				for(int j=cury+1;j<N;j++) {
					if(array[curx][j]==2) break;
					if(array[curx][j]==1) {
						return;
					}
				}
				// 좌 검색
				for(int j=cury-1;j>=0;j--) {
					if(array[curx][j]==2) break;
					if(array[curx][j]==1) {
						return;
					}
				}
			}
			flag= true;
			return ;
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(array[i][j]==3) {
					array[i][j]=2;
					start(c+1);
					array[i][j]=3;
				}
			}
		}

		
	}

}

백트래킹을 어떻게 풀어야될지 슬슬 감이 오기시작해서 기부니가좋아졌따.. ㅎㅎ;;