[SWEA-4014] 활주로 건설

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

SW Expert Academy

이 문제는 SWEA에 있는 SW 모의 역량 테스트 문제이다. 

맵의 크기와 모양이 주어지고, X의 크기가 주어진다. 활주로를 만들기 위해서 경사가 있다면 경사면을 처리해주어야 하는데, 그 경사면의 x축이 X이상이어야 하고, 한 활주로에 경사면이 겹칠수는 없다.

 

코드를 살펴보자면,

1. 가로로 탐색

2. 세로로 탐색

이 두가지가 가장 큰 축이다.

 

1과 2는 거의 동일하므로, 1만 가지고 코드를 뜯어보았다.

1) 지도를 가로로 돌면서 

2) 나랑 다른 높이의 길이 나오면 경사로 만들 수 있는지 검사.

  2-1) 나보다 높은 길이 나오면 뒤로 X만큼 돌면서 활주로 만들 수 있는지 검사,

  2-2) 나보다 낮은 길이 나오면 앞으로 검사.

3) 가로로 갈 수 있는 곳 끝까지 도달했다면 만들 수 있는 활주로!

 

for문이 복잡해서 코드가 조금 보기 지저분 할 수는 있지만 주석을 따라가다보면 읽을 수 있다:)

 

import java.util.Scanner;

public class 활주로건설 { //SWEA
	static int N,X;
	static int[][] map;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt(); //지도 크기
			X = sc.nextInt(); //활주로 거리
			int cnt = 0;
			
			map = new int[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			//가로로 탐색
			for(int i=0; i<N; i++) {
				int num = map[i][0];
				boolean[] check = new boolean[N];
				out: for(int j=1; j<N; j++) {
					if(map[i][j] >= num+2 || map[i][j] <= num-2) //높이 차이 2이상이면 사용 X.
						break out;
					else if(num+1 == map[i][j]){ //이번에 나온 수가 전 수보다 1 클 때.
						for(int k=1; k<X+1; k++) { //바로 이전 K개 검사.
							//검사 안끝났는데 범위 벗어나거나 전꺼랑 값이 다르거나 이미 경사로 만들어져 있으면 활주로 사용X.
							if (j-k < 0 || map[i][j-k] != num || check[j-k])
								break out;
						}
						for(int k=1; k<X+1; k++) { //바로 이전 K개 경사로로 사용하기
							if (map[i][j-k] == num)
								check[j-k] = true;
						}
						num = map[i][j];
					}
					else if(num-1 == map[i][j]) { //이번에 나온 수가 전 수보다 1 작으면
						for(int k=0; k<X; k++) {
							//검사 안끝났는데 범위 벗어나거나 전꺼 -1이랑 값이 다르면 활주로 사용X.
							if(j+k >= N || map[i][j+k] != num-1 || check[j+k]) 
								break out;
						}
						for(int k=0; k<X; k++) { //바로 다음 K개 경사로로 사용하기
							if (map[i][j+k] == num-1)
								check[j+k] = true;
						}
						
						j = j+X-1;
						num = map[i][j];
					}
					if(j == N-1) { //j가 끝까지 왔으면 활주로 사용 가능.
						cnt += 1;
//						System.out.println(i);
					}
				}
			}
			
			//세로로 탐색
			for(int j=0; j<N; j++) {
				int num = map[0][j];
				boolean[] check = new boolean[N];
				out: for(int i=1; i<N; i++) {
					if(map[i][j] >= num+2 || map[i][j] <= num-2) //높이 차이 2이상이면 사용 X.
						break out;
					else if(num+1 == map[i][j]){ //이번에 나온 수가 전 수보다 1 클 때.
						for(int k=1; k<X+1; k++) { //바로 이전 K개 검사.
							//검사 안끝났는데 범위 벗어나거나 전꺼랑 값이 다르거나 경사로가 이미 만들어져 있으면 활주로 사용X.
							if (i-k < 0 || map[i-k][j] != num || check[i-k])
								break out;
						}
						for(int k=1; k<X+1; k++) { //바로 다음 K개 경사로로 사용하기
							if (map[i-k][j] == num)
								check[i-k] = true;
						}
						
						num = map[i][j];
					}
					else if(num-1 == map[i][j]) { //이번에 나온 수가 전 수보다 1 작으면
						for(int k=0; k<X; k++) {
							//검사 안끝났는데 범위 벗어나거나 전꺼 -1이랑 값이 다르거나 이미 경사로 생성되어 있으면 활주로 사용X.
							if(i+k >= N || map[i+k][j] != num-1 || check[i+k]) 
								break out;
						}
						for(int k=0; k<X; k++) { //바로 다음 K개 경사로로 사용하기
							if (map[i+k][j] == num-1)
								check[i+k] = true;
						}
						i = i+X-1;
						num = map[i][j];
					}
					if(i == N-1) { //j가 끝까지 왔으면 활주로 사용 가능.
						cnt += 1;
//						System.out.println(j);
					}
				}
			}
			
			System.out.println("#"+tc+" "+cnt);
		}
	}

}