백준 14890 - 경사로
Updated:
Java
14890 번 - 경사로
문제
접근 방법
가로 n줄, 세로 n줄을 확인하여 끝까지 갈 수있는지 확인하는 문제이다.
따라서 가로, 세로 한줄 씩 뽑아내고 끝까지 갈 수있는지 확인하는 메서드를 만들어 한줄 씩 확인한다.
각 줄의 인덱스 1부터 n-1까지 바로 이전 높이와 확인하여
- 높이가 2 이상 차이나는지
- 현재 높이가 이전 높이보다 작은지
- 현재 높이가 이전 높이보다 높은지
를 확인한다.
1번의 경우 경사로를 놓을 수 없으므로 메서드를 리턴한다.
2번의 경우 현재 위치에서 앞으로 m - 1개 크기까지 경사로를 놓을 수 있는지 확인하고 가능하면 boolean 배열에 놓았다고 표시한다.
3번의 경우 현재 위치에서 뒤로 m개 크기까지 경사로를 놓을 수 있는지 확인한다. 2번에서 놓은 경사로가 있는지 확인하는 조건이 추가된다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = stoi(stk.nextToken());
m = stoi(stk.nextToken());
int[][] map = new int[n][n];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
map[i][j] = stoi(stk.nextToken());
}
}
int[] curR = new int[n];;
// 가로 탐색
for(int line = 0; line < n; line++) {
curR = map[line].clone();
if(isPass(curR))
result++;
}
// 세로 탐색
for(int i = 0; i < n; i++) {
// 세로 줄 하나를 뽑아낸다.
for(int j = 0; j < n; j++)
curR[j] = map[j][i];
if(isPass(curR))
result++;
}
System.out.println(result);
br.close();
}
// 한 줄이 지나갈 수 있는지 확ㅇ니
static boolean isPass(int[] curR) {
boolean[] vis = new boolean[n];
int h;
// 1번째 위치부터 n - 1까지 이동한다.
for(int i = 1; i < n; i++) {
if(Math.abs(curR[i] - curR[i - 1]) >= 2) {
return false;
}
// 내리막길이면
else if(curR[i - 1] > curR[i]) {
h = curR[i];
vis[i] = true;
// 현재 위치에서 내리막길을 만들 수 있는지 확인
for(int j = 1; j < m; j++) {
// 범위를 벗어났거나, 같은 높이가 아닐 때
if(!isIn(i + j) || h != curR[i + j])
return false;
vis[i + j] = true;
}
}
else if(curR[i - 1] < curR[i]) {
h = curR[i - 1];
if(vis[i - 1])
return false;
for(int j = 1; j < m; j++) {
// 범위를 벗어났거나, 경사로를 놓을 자리에 이미 놓았거나, 같은 높이가 아닐 때
if(!isIn(i - 1 - j) || vis[i - 1 - j] || h != curR[i - 1 - j])
return false;
}
}
}
return true;
}
static boolean isIn(int idx) {
if(0 <= idx && idx < n)
return true;
return false;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}