백준 14890 : 경사로

https://www.acmicpc.net/problem/14890

14890번: 경사로

[ 문제풀이 ]

모든 행/열을 돌면서 경사로를 놓을 수 있는지를 확인하면 되는 문제이다. 경사로를 놓는 조건이 조금 까다롭기 때문에 난이도가 조금 있는 것 같다.

​행/열을 확인하는 함수를 2개 구현하지 말고 1방향으로 통일하자. 행을 열로 바꿔준다면 열을 확인하는 함수 1개만 구현해 주면 훨씬 편할 것이다.

​경사로를 놓을 수 있는지 판단하는 조건은 총 3개이다. 이를 편하게 관리하기 위해 현재 사용할 수 있는 거리를 따로 저장해서 사용하자.

​1. 이전 경사로 높이 = 현재 경사로 높이 → 사용할 수 있는 거리 + 1

if (map[i][j] == temp) {
	dist++;
	continue;
}

2. 오르막길 → 현재 사용할 수 있는 거리가 L보다 크거나 같다면 사용할 수 있는 거리를 1로 만들어주고 넘어감. 만약 L보다 작다면 경사로를 설치할 수 없기 때문에 불가능

if (map[i][j] > temp) {
	if (dist >= L) {
		dist = 1;
		temp = map[i][j];
	} else {
		flag = false;
		break;
	}
}

3. 내리막길 → 현재 위치 + 경사로를 놓을 거리가 범위를 벗어난다면 불가능. 범위를 벗어나지 않는다면 현재 위치부터 +L 칸까지 돌면서 각 칸의 높이가 같은지 확인

if (j + L > N) {
	flag = false;
	break;
} else {
	int k = 0;
	boolean flag2 = true;
						
	for (k = j + 1; k < j + L; ++k) {
	    if (map[i][j] != map[i][k]) {
			flag2 = false;
		}
	}
						
	if (!flag2) {
		flag = false;
		break;
	} else {
		j = k - 1;
		temp = map[i][j];
		dist = 0;
	}
}

전체 소스코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, L;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());

		map = new int[N << 1][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());
			}
		}
		
		//세로 방향 -> 가로 방향
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[N + i][j] = map[j][i];
			} 
		}
		
		bw.write(getAnswer() + "\n");
		bw.flush();bw.close();br.close();
	}

	public static int getAnswer() {
		int answer = 0;

		for (int i = 0; i < N << 1; ++i) {
			boolean flag = true;
			int temp = map[i][0];
			int dist = 1; //사용 가능한 거리
			
			for (int j = 1; j < N; ++j) {
				//높이 차이가 1보다 크다면
				if (Math.abs(map[i][j] - temp) > 1) {
					flag = false;
					break;
				}
				
				//높이가 같다면 사용 가능한 거리 +1
				if (map[i][j] == temp) {
					dist++;
					continue;
				}
				
				//오르막길인 경우
				if (map[i][j] > temp) {
					if (dist >= L) {
						dist = 1;
						temp = map[i][j];
					} else {
						flag = false;
						break;
					}
				} 
				//내리막길인 경우
				else {
					//우측 범위를 벗어나는 경우
					if (j + L > N) {
						flag = false;
						break;
					} else {
						int k = 0;
						boolean flag2 = true;
						
						for (k = j + 1; k < j + L; ++k) {
							if (map[i][j] != map[i][k]) {
								flag2 = false;
							}
						}
						
						if (!flag2) {
							flag = false;
							break;
						} else {
							j = k - 1;
							temp = map[i][j];
							dist = 0;
						}
					}
				}
			}
			if (flag) answer++;
		}
		return answer;
	}
}