알고리즘매일매일

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

나는 그냥 문제에 나와있는대로 하나하나 처리를 해줬는데 다른 사람들의 풀이를 보니까 더 간단하게 풀었던데 나중에 보고 다시 공부해봐야겠다.

먼저 가로방향과 세로방향을 각각 구해줬다.

가로 방향을 구할 때는 모든 행에 대해서 각각의 열을 비교하였다.

1. j열과 j+1 의 높이가 같다면 다음 열의 비교로 넘어간다.
2. 높이 차이가 1보다 크다면 경사로를 놓을 수도 없으므로 해당 행에는 활주로 건설이 불가능하다.
3. 높이차이가 1이라면 경사로를 놓을 수 있는지 확인한다. 밑의 조건에 맞지 않는다면 flag를 false로 바꿔준다.
   1. 경사로의 길이 x만큼을 놓았을 때 범위를 넘어가지 않는지 확인.
   2. 경사로를 놓아줄 x만큼의 칸의 높이가 같은지 확인.
   3. 경사로를 놓을 자리에 이미 경사로가 놓여있지 않은지 확인.
4. 위의 조건을 모두 통과하였다면 경사로를 놓아줄 것인데 j가 j+1보다 컸다면 j+1부터 뒷쪽으로 경사로를 놓아주면 되고, 반대의 경우에는 j부터 앞쪽으로 경사로를 놓아주면 된다.
5.  
6. 행의 열 끝까지가는 동안 flag가 true라면 (위의 조건에서 한번도 걸리지 않았다면) 해당 행은 활주로를 건설할 수 있다.

위와 같은 방식으로 세로 방향도 행과 열을 바꿔서 구해주면된다. 

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

처리해줘야 할 조건이 꽤 많은 문제였다.

1. 높이가 같아서 경사로를 안 놓아도 되는지
2. 높이가 다르다면 높이 차이가 2보다 적게 나서 경사로를 놓아줄 수 있는지
3. 경사로를 놓을 때 경사로가 범위를 벗어나지 않는지
4. 경사로를 놓는 곳의 높이는 같은지
5. 경사로가 이미 놓여져있지는 않은지

위의 조건들을 각 행과 열에 대해서 모두 검사해주어야 한다.

모든 행을 검사해주는 checkGaro와 모든 열을 검사해주는 checkSero 함수를 만들어서 테스트 케이스별로 각각 한 번씩 호출해서 답을 구하도록 했다. 각 행이나 열마다 위의 모든 조건을 만족하면 count를 해줬다.

더 자세한 설명은 코드의 주석 참고

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

public class Solution {

	static int N,X,count;
	static int[][] map;
    
	static boolean[][] garo;
	static boolean[][] sero;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			X = Integer.parseInt(st.nextToken());
			map = new int[N][N];
            
             //해당 위치에 경사로가 있는지 체크해줄 배열
			garo = new boolean[N][N];
			sero = new boolean[N][N];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			count = 0;
			
            //모든 행 검사
			checkGaro();
            
            //모든 열 검사
			checkSero();
			
			System.out.println("#"+tc+" "+count);
		}
	}
	
	static void checkGaro() {
		
		
		//모든 행을 검사 
		for(int i=0; i<N; i++) {
			boolean ok = true;
			
			//각 행에서 높이를 검사 
			for(int j=0; j<N-1; j++) {
				
                //높이가 같다면 다음 칸 비교로 넘어간다.
				if(map[i][j] == map[i][j+1]) {
					continue;
				}
				
                //앞의 칸이 뒤의 칸보다 더 큰 경우
				if(map[i][j] > map[i][j+1]) {
					if(map[i][j] - map[i][j+1] > 1) {
						//차이가 1보다 커서 경사로를 놓을 수 없다. 
						ok = false;
						break;
					}
					
					if(j+X >= N) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=j+1; k<=j+X; k++) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i][j+1] != map[i][k]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(garo[i][k]) {
							ok = false;
							break;
						}
					}
					
                    
                    //바로 위의 반복문에서 ok는 false값으로 break되어 나올 경우 break해준다.
					if(!ok) break;
					
                    
					//경사로를 놓는다.
					for(int k=j+1; k<=j+X; k++) {
						garo[i][k] = true;
					}
					
					
					//뒤의 칸이 앞의 칸보다 큰 경우
				} else if(map[i][j] < map[i][j+1]) {
					if(map[i][j+1] - map[i][j] > 1) {
						ok = false;
						break;
					}
					
					if(j+1-X < 0) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=j; k>=j+1-X; k--) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i][j] != map[i][k]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(garo[i][k]) {
							ok = false;
							break;
						}
					}
					
					if(!ok) break;
					
					//경사로를 놓는다.
					for(int k=j; k>=j+1-X; k--) {
						garo[i][k] = true;
					}
				}
	
			}
			
            //해당 행이 모든 조건을 만족하여 ok가 true 값을 가지면 count값을 증가
			if(ok) count++;
		}
	}
	
	static void checkSero() {
		
		//모든 열을 검사 
		for(int j=0; j<N; j++) {
			boolean ok = true;
			
			//각 열에서 높이를 검사 
			for(int i=0; i<N-1; i++) {
				
                //높이가 같다면 다음 칸으로 넘어간다.
				if(map[i][j] == map[i+1][j]) {
					continue;
				}
				
                //앞의 칸이 뒤의 칸보다 더 큰 경우
				if(map[i][j] > map[i+1][j]) {
					if(map[i][j] - map[i+1][j] > 1) {
						//차이가 1보다 커서 경사로를 놓을 수 없다. 
						ok = false;
						break;
					}
					
					if(i+X >= N) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=i+1; k<=i+X; k++) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i+1][j] != map[k][j]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(sero[k][j]) {
							ok = false;
							break;
						}
					}
					
					if(!ok) break;
					
					//경사로를 놓는다.
					for(int k=i+1; k<=i+X; k++) {
						sero[k][j] = true;
					}
					
					
				//뒤의 칸이 앞의 칸보다 더 큰 경우
				} else if(map[i][j] < map[i+1][j]) {
					if(map[i+1][j] - map[i][j] > 1) {
						ok = false;
						break;
					}
					
					if(i+1-X < 0) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=i; k>=i+1-X; k--) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i][j] != map[k][j]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(sero[k][j]) {
							ok = false;
							break;
						}
					}
					
					if(!ok) break;
					
					//경사로를 놓는다.
					for(int k=i; k>=i+1-X; k--) {
						sero[k][j] = true;
					}
				}
						
			}
			
			if(ok) count++;
		}
	}

}