[SWEA] 활주로건설

중간에 예외케이스 때문에 시간을 잡아먹었다ㅠ

문제를 작게 나눌수록 쉬워진다.
1. 가로/세로 나누기

		//가로 검색
		for(int i=0; i<N; i++) {
			for (int j = 0; j < N; j++) {
				temp[j] = map[i][j];
			}
			find(temp);
		}
		
		//세로 검색
		for(int j=0; j<N; j++) {
			for (int i = 0; i < N; i++) {
				temp[i] = map[i][j];
			}
			find(temp);
		}	

temp에 가로와 세로의 한줄의 활주로를 담아서 find함수에 넘겨준다.
실질적으로 이 활주로가 사용가능한지는 find에서 결정한다.

제일먼저 current를 지정해준다. 맨 처음의 원소에서 시작해서(temp[0]) 그 다음 원소랑 계속해서 비교한다. 같으면 그냥 넘어가지만 숫자가 다르다면
2. 해당 원소들끼리의 차이가 1인가? 1보다 큰가?를 판별해준다. 만약 1보다 크다면 경사로를 놓아도 활주로가 불가능하기 때문에 바로 return하지만 1이라면 또 다시 경우의 수를 나눠주어야한다.
3. 1차이만 난다면 높->낮인지 낮->높인지 판단해주어야 한다.
4. 만약 높->낮이라면 낮은 곳(j:i이후)들이 X만큼 이어지는지 판단해야한다. 그렇지 않다면 바로 return해주면 된다.

for(int j=i; j<X+i; j++) {
	if(temp[j] != temp[i] || isSelected[j]) {
		flag = false;
		return;
	}
	isSelected[j] = true;
}

5. 만약 낮->높이라면 낮은 곳(j:i이전)들이 X만큼 이어지는지 판단해야한다. 그렇지 않다면 바로 return해주면 된다.

for(int j=i-1; j>=i-X; j--) {
	if(temp[j]!=current || isSelected[j]) {
		flag = false;
		return;
	}
}

이렇게만 생각하면 엄청난 예외가 나온다.
바로 경사로가 겹칠때를 생각해주지 못한다.
그렇기 때문에 isSelected라는 boolean 배열 변수를 만들어서 경사로를 놓은 곳에 true로 변환해주어야 한다. 만약 경사로를 놓을 곳이 true라면 경사로를 놓을 수 없다.

package com.study.classAlgo;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SWEA_4014_활주로건설 {
	static int N, X, result;
	static int[][] map;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			X = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			result = 0;
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			solve();
			System.out.println("#"+t+" "+result);
		}
		
	}
	
	private static void solve() {
		int[] temp = new int[N];
		
		//가로 검색
		for(int i=0; i<N; i++) {
			for (int j = 0; j < N; j++) {
				temp[j] = map[i][j];
			}
			find(temp);
		}
		
		//세로 검색
		for(int j=0; j<N; j++) {
			for (int i = 0; i < N; i++) {
				temp[i] = map[i][j];
			}
			find(temp);
		}	
	}

	private static void find(int[] temp) {
		int current = temp[0];
		boolean[] isSelected = new boolean[N];
		boolean flag = true;
		
		for(int i=1; i<N; i++) {
			if(current != temp[i]) {
				if(Math.abs(current-temp[i])>1) {//1차이 이상
					return;
				}else if(temp[i]+1 == current){//높->낮
					if(X+i<=N) {
						for(int j=i; j<X+i; j++) {
							if(temp[j] != temp[i] || isSelected[j]) {
								flag = false;
								return;
							}
							isSelected[j] = true;
						}
					}else {
						return;
					}
					current = temp[i];
				}else if(current+1 == temp[i]) {//낮->높
					if(i-X >=0) {
						for(int j=i-1; j>=i-X; j--) {
							if(temp[j]!=current || isSelected[j]) {
								flag = false;
								return;
							}
						}
					}else {
						return;
					}
					current = temp[i];
				}
			}
		}
		if(flag) {
			result++;
		}
	}
}