알고리즘 문제 풀이

SWEA 활주로 건설 (JAVA 자바)

superbono 2021. 4. 12. 18:38

문제 출처: 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE&problemTitle=%ED%99%9C%EC%A3%BC%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

import java.util.Scanner;

public class swea_활주로건설 {
	static int map[][];
	static boolean visited[][];
	static int res;
	static int N, X;
	static boolean isPossible;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			X = sc.nextInt();
			res = 0;
			
			map = new int [N][N];
			visited = new boolean[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++) {
				isPossible = true;
				for (int j = 1; j < N; j++) {
					if(!isPossible) break;
					int tmp = Math.abs(map[i][j] - map[i][j - 1]);
					if(tmp > 1) { 
						isPossible = false;
						break;
					}else if(tmp == 1) {
						
						if(map[i][j] > map[i][j - 1]) {
							for (int k = j - 1; k > j - 1 - X; k--) {
								if( k < 0 || visited[i][k] || map[i][j - 1] != map[i][k]) {
									isPossible = false;
									break;
								}
								visited[i][k] = true;
							}
						}else { 
							for (int k = j; k < j + X; k++) {
								if(k >= N || visited[i][k] || map[i][j] != map[i][k]) {
									isPossible = false;
									break;
								}
								visited[i][k] = true;
							}
						}
					}
				}
				if(isPossible)
					res++;
			}
			// 열 탐색
			visited = new boolean[N][N];
			for (int j = 0; j < N; j++) {
				isPossible = true;
				for (int i = 1; i < N; i++) {
					int tmp = Math.abs(map[i][j] - map[i - 1][j]);
					if(tmp > 1) { 
						isPossible = false;
						break;
					}else if(tmp == 1) { 
						if(map[i][j] > map[i - 1][j]) {
							for (int k = i - 1; k > i - 1 - X; k--) {
								if(k < 0 || visited[k][j] || map[i - 1][j] != map[k][j]) {
									isPossible = false;
									break;
								}
								visited[k][j] = true;
							}
						}else { 
							for (int k = i; k < i + X; k++) {
								if(k >= N || visited[k][j] || map[i][j] != map[k][j]) {
									isPossible = false;
									break;
								}
								visited[k][j] = true;
							}
						}
					}
				}
				if(isPossible)
					res++;
			}
			System.out.println("#" + tc + " " + res);
		}
		
	}
}

// 자세히 보면 열 탐색과 행 탐색은 열과 행만 바뀔 뿐 중복되는 코드이기 때문에 코드의 길이를 절반으로 줄일 수도 있다.