[JAVA] SWEA 4014 활주로 건설

전체 코드

import java.util.Scanner;

public class SWEA_4014_활주로건설 {

	static int N, T, X, CNT;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();

		for (int test = 1; test <= T; test++) {
			CNT = 0;
			N = sc.nextInt();
			X = sc.nextInt();

			int arr[][] = new int[N][N];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}

			for (int i = 0; i < N; i++) {
				chk(arr[i]);
			}

			for (int i = 0; i < N; i++) {
				int tmp[] = new int[N];
				for (int j = 0; j < N; j++) {
					tmp[j] = arr[j][i];
				}
				chk(tmp);
			}
			
			System.out.println("#"+test+ " " + CNT);

		}
	}

	private static void chk(int[] arr) {
		// check
		int f = arr[0];
		boolean chk = false;
		
		for (int i = 0; i < N; i++) { // 모두 같은 수인지 체크, 모두 같으면 가능하므로 빨리끝내기 위함
			if (f != arr[i]) {
				chk = true;
				break;
			}
		}
		
		if(!chk) {
			CNT++;
			return;
		}

		int cnt = 0;
		int now;
		for (int i = 0; i < N; i++) {
			now = arr[i];
			if (now == f)
				cnt++;
			else {
				if(now == f+1) { //높아질 때, 지나온 길에 설치하는 것이므로 인덱스 변화 x
					if(cnt>=X){//건설가능
						cnt = 1;
					}else// 건설불가
						return;
					
				}else if(now == f-1) { //낮아질때, 앞에 설치할 수 있는지 체크해야 하므로 인덱스 추가
					if(i + X - 1 < N) { //건설가능, 앞에 길 있는지 체크
						for(int j = i; j<i+X; j++) {
							if(arr[j] != now)
								return;
						}
						cnt  = 0;
						i = i + X-1;
					}else
						return;
				}else
					return;
				
				f = now;
			}
			
		}
		CNT++;
	}

}

 

문제 핵심 코드

 

private static void chk(int[] arr) {
	// check
	int f = arr[0];
	boolean chk = false;
	
	for (int i = 0; i < N; i++) { // 모두 같은 수인지 체크, 모두 같으면 가능하므로 빨리끝내기 위함
		if (f != arr[i]) {
			chk = true;
			break;
		}
	}
	
	if(!chk) {
		CNT++;
		return;
	}

	int cnt = 0;
	int now;
	for (int i = 0; i < N; i++) {
		now = arr[i];
		if (now == f)
			cnt++;
		else {
			if(now == f+1) { //높아질 때, 지나온 길에 설치하는 것이므로 인덱스 변화 x
				if(cnt>=X){//건설가능
					cnt = 1;
				}else// 건설불가
					return;
				
			}else if(now == f-1) { //낮아질때, 앞에 설치할 수 있는지 체크해야 하므로 인덱스 추가
				if(i + X - 1 < N) { //건설가능, 앞에 길 있는지 체크
					for(int j = i; j<i+X; j++) {
						if(arr[j] != now)
							return;
					}
					cnt  = 0;
					i = i + X-1;
				}else
					return;
			}else
				return;
			
			f = now;
		}
		
	}
	CNT++;
}

 

chk함수에 배열만 넣으면 해당 열 또는 행을 체크할 수 있도록 설계 했다.

 

높이가 높아질 때와 낮아질 때 두가지 경우를 나눠서 생각하면 쉬운 문제였다.

 

높아질 땐 지나온 경로이므로 그동안의 카운트가 X보다 크거나 같은지를 체크해 경사로를 설치할 수 있는지 체크하고,

 

낮아질 땐 현재 위치의 앞에 X칸 만큼의 높이가 현재 높이와 같은지 체크한다.

 

이 두가지 경우를 생각하는 것이 문제의 핵심이었다!