14890_경사로

사용 알고리즘: 구현 빡

사용 언어: java

 

package week03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_bj_14890_경사로 {
	static int n, l;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken()); //맵 크기
		l = Integer.parseInt(st.nextToken()); //경사로의 가로 길이
		
		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] = Integer.parseInt(st.nextToken());
			}
		}
		//입력 끝
		
		int ans = 0;
		
		//가로 길 확인 map[i][?]
		for (int i = 0; i < n; i++) {
			if(validRowRoad(i)) ans++;
		}
		
		//세로 길 확인 map[?][j]
		for (int j = 0; j < n; j++) {
			if(validColRoad(j)) ans++;
		}
		
		System.out.println(ans);
	}

	private static boolean validColRoad(int col) {
		boolean[] lamp = new boolean[n];
		ArrayList<int[]> al = new ArrayList<>(); // {위쪽 idx, 아래쪽 idx, 높은 방향}
		
		for (int i = 0; i < n - 1; i++) {
			int gap = Math.abs(map[i][col] - map[i+1][col]);
			if (gap > 1) return false;
			if (gap == 1) al.add(new int[] {i, i+1, map[i][col] - map[i+1][col]});
		}
		
		for (int i = 0; i < al.size(); i++) {
			int[] tmp = al.get(i);
			
			// [0, 1, 1] [2, 3, 1] 
			if (tmp[2] > 0) { //위쪽이 더 높다면, 아래쪽으로 l개만큼 경사로 놓기
				for (int build = tmp[1]; build < tmp[1] + l; build++) {
					if(build >= n) return false; //범위 넘어가서 경사로를 놓을 수 없음
					if(lamp[build]) return false; //이미 경사로가 설치돼서 중복 설치할 수 없음
					lamp[build] = true;
				}
			}
			else { //아래쪽이 더 높다면, 위쪽으로 l개만큼 경사로 놓기
				for (int build = tmp[0]; build > tmp[0] - l; build--) {
					if(build < 0) return false;
					if(lamp[build]) return false;
					lamp[build] = true;
				}
			}
		}
		return true;
	}

	private static boolean validRowRoad(int row) {
		//경사로를 두었는지 확인하는 배열 , 차이나는 인덱스끼리 저장하는 리스트
		boolean[] lamp = new boolean[n];
		ArrayList<int[]> al = new ArrayList<>(); // {왼쪽 idx, 오른쪽 idx, 높은 방향}
		
		for (int j = 0; j < n - 1; j++) {
			int gap = Math.abs(map[row][j] - map[row][j+1]);
			if (gap > 1) return false;
			//왼쪽이 더 높으면 양수, 오른쪽이 더 높으면 음수
			if (gap == 1) al.add(new int[] {j, j+1, map[row][j] - map[row][j+1]});
		}
		//
		
		for (int i = 0; i < al.size(); i++) {
			int[] tmp = al.get(i);
			
			if (tmp[2] > 0) { //왼쪽이 더 높다면, 오른쪽으로 l개만큼 경사로 놓기
				for (int build = tmp[1]; build < tmp[1] + l; build++) {
					if(build >= n) return false; //범위 넘어가서 경사로를 놓을 수 없음
					if(lamp[build]) return false; //이미 경사로가 설치돼서 중복 설치할 수 없음
					lamp[build] = true;
				}
			}
			else { //오른쪽이 더 높다면, 왼쪽으로 l개만큼 경사로 놓
				for (int build = tmp[0]; build > tmp[0] - l; build--) {
					if(build < 0) return false;
					if(lamp[build]) return false;
					lamp[build] = true;
				}
			}
		}
		return true;
	}

}

 

아웅.. l을 안 넣고 이상한 상수를 넣어서 답이 안 나왔었다

논리는 아주 맞았따 칭찬해