경사로 (14890)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 경사로는 높이 1, 길이 L이다.
2. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
3. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
4. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

2.2 풀이

위에서 정리한 조건에 부합하게 경사로를 설치해서
각 행과 열에 대해서 하나씩 지날 수 있는 길인지 체크해서 카운팅하는 문제입니다.

문제는 경사로 설치 구현이겠죠.
제가 구현한 방식은 이렇습니다.

        // 경사로를 설치할 수 있는지 체크하고, 
	// 설치할 수 있다면 설치하고 true 리턴
	// 설치할 수 없다면 false 리턴
	static boolean isFit(int y, int x, int dir) {
		// 이미 설치돼있을 때
		if (fit[y][x]) return false;
		
		// 원본 좌표 저장
		int oriY = y; 
		int oriX = x;
		
		// 이전 좌표의 높이
		int prev = M[y][x];
		
		// 경사로의 길이만큼 체크
		for (int i = 0; i < L - 1; i++) {
			y += my[dir];
			x += mx[dir];
			
			// 도로를 벗어났을 때
			if (y < 0 || y >= N || x < 0 || x >= N) return false;
			
			// 이전 좌표의 높이와 현재 좌표의 높이가 다를 때
			if (prev != M[y][x]) return false;
			
			// 이미 설치했을 때
			if (fit[y][x]) return false;
			
			// 이전 좌표의 높이 갱신
			prev = M[y][x];
		}
		
		//  설치할 수 있다면 경사로를 설치
		y = oriY;
		x = oriX;
		
		fit[y][x] = true;
		for (int i = 0; i < L - 1; i++) {
			y += my[dir];
			x += mx[dir];
			fit[y][x] = true;
		}
		
		return true;
	}

설치할 좌표와 설치할 방향을 인자로 받아서 설치할 수 있는지 체크하고
설치가 가능하면 설치를 하는 함수입니다.
이 함수를 각 행과 열을 체크할 때 호출함으로서 지날 수 있는 도로인지 판별할 수 있습니다.

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, L, M[][], my[] = {-1, 0, 1, 0}, mx[] = {0, 1, 0, -1};
	static boolean[][] fit;
	
	// 경사로를 설치할 수 있는지 체크하고, 
	// 설치할 수 있다면 설치하고 true 리턴
	// 설치할 수 없다면 false 리턴
	static boolean isFit(int y, int x, int dir) {
		// 이미 설치돼있을 때
		if (fit[y][x]) return false;
		
		// 원본 좌표 저장
		int oriY = y; 
		int oriX = x;
		
		// 이전 좌표의 높이
		int prev = M[y][x];
		
		// 경사로의 길이만큼 체크
		for (int i = 0; i < L - 1; i++) {
			y += my[dir];
			x += mx[dir];
			
			// 도로를 벗어났을 때
			if (y < 0 || y >= N || x < 0 || x >= N) return false;
			
			// 이전 좌표의 높이와 현재 좌표의 높이가 다를 때
			if (prev != M[y][x]) return false;
			
			// 이미 설치했을 때
			if (fit[y][x]) return false;
			
			// 이전 좌표의 높이 갱신
			prev = M[y][x];
		}
		
		//  설치할 수 있다면 경사로를 설치
		y = oriY;
		x = oriX;
		
		fit[y][x] = true;
		for (int i = 0; i < L - 1; i++) {
			y += my[dir];
			x += mx[dir];
			fit[y][x] = true;
		}
		
		return true;
	}
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		L = Integer.parseInt(s[1]);
		M = new int[N][N];
		fit= new boolean[N][N];
		
		int r, c, cnt = 0;
		
		for (r = 0; r < N; r++) {
			s = br.readLine().split(" ");
			for (c = 0; c < N; c++)
				M[r][c] = Integer.parseInt(s[c]);
		}
		
		// 행 검사
		out: 
		for (r = 0; r < N; r++) {
			int prev = M[r][0];
			
			for (c = 1; c < N; c++) {
				int cur = M[r][c];
				
				// 이전 좌표의 높이와 현재 좌표의 높이의 차이가 1보다 클 때
				if (Math.abs(cur - prev) > 1) continue out;
				
				// 현재 좌표가 이전 좌표보다 1크고 이전 좌표로부터 서쪽으로 경사로 설치가 불가능할 때
				if (cur > prev && !isFit(r, c - 1, 3)) continue out;
				
				// 현재 좌표가 이전 좌표보다 1작고 현재 좌표로부터 동쪽으로 경사로 설치가 불가능할 때
				if (cur < prev && !isFit(r, c, 1)) continue out;
				
				prev = cur;
			}
			
			cnt++;
		}
		
		// 설치했던 경사로 모두 제거
		for (r = 0; r < N; r++)
			for (c = 0; c < N; c++)
				fit[r][c] = false;
		
		// 열 검사
		out: 
		for(c = 0; c < N; c++) {
			int prev = M[0][c];
			
			for (r = 1; r < N; r++) {
				int cur = M[r][c];
				
				// 이전 좌표의 높이와 현재 좌표의 높이의 차이가 1보다 클 때
				if (Math.abs(cur - prev) > 1) continue out;
				
				// 현재 좌표가 이전 좌표보다 1크고 이전 좌표로부터 북쪽으로 경사로 설치가 불가능할 때
				if (cur > prev && !isFit(r - 1, c, 0)) continue out;
				
				// 현재 좌표가 이전 좌표보다 1작고 현재 좌표로부터 남쪽으로 경사로 설치가 불가능할 때
				if (cur < prev && !isFit(r, c, 2)) continue out;
				
				prev = cur;
			}
			
			cnt++;
		}
		
		bw.write(cnt + "");
		bw.close();
	}
}