SWEA 4014 - 활주로 건설

Java

4014 번 - 활주로 건설

문제

경사로의 길이 X 와 절벽지대의 높이 정보가 주어질 때,
활주로를 건설할 수 있는 경우의 수를 계산하는 프로그램을 작성하라.

• N 의 크기는 6 이상 20 이하의 정수이다. ( 6 ≤ N ≤ 20 )
• 경사로의 높이는 항상 1 이고, 길이 X 는 2 이상 4 이하의 정수이다. ( 2 ≤ X ≤ 4 )
• 지형의 높이는 1 이상 6 이하의 정수이다.
• 동일한 셀에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.

접근 방법

행 단위로 탐색하는 경우와 열 단위로 탐색하는 경우를 나누어 생각을 해보았다.

각 행/열 마다 차례로 탐색하면서, 각 값과 이전 값을 비교한다.
비교하면 총 4가지의 경우가 있는데

1. 이전 높이와 현재 높이가 같은 경우
2. 현재 높이가 이전 높이보다 1 큰 경우
3. 현재 높이가 이전 높이보다 1 작은 경우
4. 높이 차이가 2 이상인 경우

1번의 경우 평평하므로, 현재까지 평평한 길이의 값을 갱신해준다.

2번의 경우 오르막 경사로를 설치하여야 하는데, 1번에서 체크한 평평한 길이의 값과 비교하여, 평평한 길이의 값이 크면 오르막 경사로를 설치 할 수 있다고 판단한다.

3번의 경우 현재부터, 경사로 길이까지 평평한지 확인한다.

4번의 경우 경사로를 설치 할 수 없으므로 실패한다.

코드

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

class Solution {
	static int result = 0;
	static int[][] map;
	static int n , x;
	static boolean[][] vis;
	public static void main(String []args) throws Exception {  
		System.setIn(new FileInputStream("res/input.txt"));	//제출 할 때 주석해야함
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		
    		stk = new StringTokenizer(br.readLine());
    		n = stoi(stk.nextToken());
    		x = stoi(stk.nextToken());
    		
    		map = new int[n][n];
    		
    		for(int i = 0; i < n; i++) {
    			stk = new StringTokenizer(br.readLine());
    			for(int j = 0; j < n; j++) {
    				map[i][j] = stoi(stk.nextToken());
    			}
    		}
    		
    		result = process();
    		
    		System.out.println("#" + tidx + " " + result);
    	}
	}
	
	private static int process() {
		int count = 0;
		for(int i = 0; i < n; i++) {
			if(makeRoadByRow(i))
				count++;
			if(makeRoadByCol(i))
				count++;
		}
		
		return count;
	}

	private static boolean makeRoadByRow(int i) {
		// 이전  높이, 현재까지 같은 높이의 길이, len : 오르막 경사를 설치 할 수 있는지의 여부를 확인
		int lastH = map[i][0] , len = 0;
		int j = 0; // 탐색 열 위치
		
		while(j < n) {
			if(lastH == map[i][j]) {
				len++;
				j++;
			}
			else if(lastH + 1 == map[i][j]) { 	// 오르막 경사로 설치 가능 판단
				if(len < x)		// 현재까지 같은 높이의 활주로 길이가 경사로보다 작은 경우
					return false;
				lastH++;
				len = 1;
				j++;
			}
			else if(lastH - 1 == map[i][j]) {	// 내리막 경사로 설치 가능 판단
				int count = 0;		// 경사로의 길이
				for(int k = j; k < n; k++) {
					if(lastH - 1 != map[i][k]) {	// 높이 차이가 1이 아닌 경우 반복문을 빠져나온다.
						break;
					}
					if(++count == x)	// 높이 차이가 1이면 경사로 길이를 증가하며, 길이가 경사로 길이 x갸 되면 종료한다.
						break;
				}
				
				if(count < x)	// 설치 할 수 있는 경사로 길이가 주어진 경사로 길이 x보다 짧으면 실패한다.
					return false;
				
				lastH--;
				len = 0;		// 현재 위치까지 경사로를 깔았으므로, 이전 위치에 경사로를 깔 수 없어 현재까지의 길이를 0으로 둔다. 
				j = j + x;
			}
			else
				return false;		
		}
		return true;
	}
	
	private static boolean makeRoadByCol(int i) {
		// 이전  높이, 현재까지 같은 높이의 길이, len : 오르막 경사를 설치 할 수 있는지의 여부를 확인
				int lastH = map[0][i] , len = 0;
				int j = 0; // 탐색 열 위치
				
				while(j < n) {
					if(lastH == map[j][i]) {
						len++;
						j++;
					}
					else if(lastH + 1 == map[j][i]) { 	// 오르막 경사로 설치 가능 판단
						if(len < x)		// 현재까지 같은 높이의 활주로 길이가 경사로보다 작은 경우
							return false;
						lastH++;
						len = 1;
						j++;
					}
					else if(lastH - 1 == map[j][i]) {	// 내리막 경사로 설치 가능 판단
						int count = 0;		// 경사로의 길이
						for(int k = j; k < n; k++) {
							if(lastH - 1 != map[k][i]) {	// 높이 차이가 1이 아닌 경우 반복문을 빠져나온다.
								break;
							}
							if(++count == x)	// 높이 차이가 1이면 경사로 길이를 증가하며, 길이가 경사로 길이 x갸 되면 종료한다.
								break;
						}
						
						if(count < x)	// 설치 할 수 있는 경사로 길이가 주어진 경사로 길이 x보다 짧으면 실패한다.
							return false;
						
						lastH--;
						len = 0;		// 현재 위치까지 경사로를 깔았으므로, 이전 위치에 경사로를 깔 수 없어 현재까지의 길이를 0으로 둔다. 
						j = j + x;
					}
					else
						return false;
				}
				return true;
	}

	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

매우 더럽게 푼 문제

개선할 점

없