[SWEA] 4014 - 활주로 건설 / [백준] 14890 - 경사로

[문제링크]

SW Expert Academy

[문제링크]

14890번: 경사로

 

 

0. 활주로 건설이 불가능한 경우는 2가지이다

  - 2칸 이상 차이가 나는 경우

  - 1칸 차이가 나지만 X칸만큼의 공간이 존재하지 않을 경우

 

1. 2칸 이상 차이가 난다면 불가능 처리한다

 

2. 높이가 동일한 경우, cnt로 갯수를 세가며 진행한다

  - 올라가야하는 상황이 생겼을 때, cnt가 X보다 크거나 같아야만 진행 가능하다

  - 올라간 칸에서부터 시작하므로 cnt값을 1로 초기화

 

3. 내려가야하는 상황이 생겼다면 앞에 X칸의 공간이 동일한 높이로 존재해야 진행 가능하다

  - 반목문으로 X칸의 높이를 확인, 다르면 불가능 처리한다

  - 전부 같다면, 현재 위치가 j였을때 j+X칸에서부터 다시 시작하므로, j+X-1으로 포인터를 옮긴다

  - 이때, j+X-1칸은 경사로의 마지막 칸이므로, cnt는 0으로 초기화

 

4. 위 과정을 모든 행/열에 대해 실행해주고 가능한 경우를 카운트

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

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int x = pint(st.nextToken());
			int[][]map = new int[n][n];

			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			
			int possibleCnt=0;
			
			for (int i = 0; i < n; i++) {
				//i번째 Row의 불가능 가능 여부를 탐색
				boolean isP = true;
				
				//1. 2칸 이상 차이나면 불가
				for (int j = 1; j < n; j++) {
					if(Math.abs(map[i][j] - map[i][j-1]) >=2)isP=false;
				}if(!isP)continue;
				
				//2. 1칸 올라|내려 가야하는데, 뒤|앞에 공간이 x칸 없으면 불가
				int prev=map[i][0];
				int cnt=1;
				for (int j = 1; j < n; j++) {
					//같으면 +
					if(prev == map[i][j])cnt++;
					else if(prev< map[i][j]) {
						//올라갈 때
						if(cnt>=x) {
							//ok
						}
						else {
							isP=false;
						}
						prev=map[i][j];
						cnt=1;//cnt초기화
					}
					else {
						//내려갈 때
						//앞에 x칸이 다 같은 높이로 존재하는지 확인
						//만족한다면, x 앞칸으로 포인터(j)이동
						prev = map[i][j];
						cnt=1;
						for (int j2 = 1; j2 < x; j2++) {
							if(j+j2 >= n)break;
							if(prev==map[i][j+j2])cnt++;
						}
						if(cnt!=x)isP=false;
						j = j+x-1;
						cnt=0;//cnt초기화
					}
				}
				if(isP)possibleCnt++;
			}
			
			for (int i = 0; i < n; i++) {
				//i번째 Col의 불가능 가능 여부를 탐색
				boolean isP = true;
				
				//1. 2칸 이상 차이나면 불가
				for (int j = 1; j < n; j++) {
					if(Math.abs(map[j][i] - map[j-1][i]) >=2)isP=false;
				}if(!isP)continue;
				
				//2. 1칸 올라|내려 가야하는데, 뒤|앞에 공간이 x칸 없으면 불가
				int prev=map[0][i];
				int cnt=1;
				for (int j = 1; j < n; j++) {
					//같으면 +
					if(prev == map[j][i])cnt++;
					else if(prev< map[j][i]) {
						//올라갈때
						if(cnt>=x) {
							//ok
						}
						else {
							isP=false;
						}
						prev=map[j][i];
						cnt=1;//cnt초기화
					}
					else {
						//내려갈 때
						//앞에 x칸이 다 같은 높이로 존재하는지 확인
						//만족한다면, x 앞칸으로 포인터(j)이동
						prev = map[j][i];
						cnt=1;
						for (int j2 = 1; j2 < x; j2++) {
							if(j+j2 >= n)break;
							if(prev==map[j+j2][i])cnt++;
						}
						if(cnt!=x)isP=false;
						j = j+x-1;
						cnt=0;
					}
					
				}
				if(isP)possibleCnt++;
			}
			
			sb.append("#").append(testcase).append(" ").append(possibleCnt).append("\n");
		}
		System.out.println(sb);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면