문제
N x N 격자에서 한 행 또는 한 열이 지나갈 수 있는 길인지 판별하라. 높이 차이가 1인 곳에 길이 L인 경사로를 놓을 수 있으며, 경사로는 겹칠 수 없다.
입력
첫째 줄에 N (2 ≤ N ≤ 100), L (1 ≤ L ≤ N), 이후 N줄에 격자의 높이가 주어진다.
출력
지나갈 수 있는 길의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 2 3 3 3 3 3 3 2 3 3 3 3 3 2 2 2 3 2 3 1 1 1 2 2 2 1 1 1 3 3 1 1 1 2 3 4 5 | 3 |
풀이
각 행과 열을 1차원 배열로 추출하여 독립적으로 검사한다.
- 각 행과 열(전치)에 대해
check()함수를 호출한다 - 같은 높이가 이어지면 카운트를 증가시킨다
- 높이가 1 증가하면: 이전 구간이 L 이상이어야 경사로를 놓을 수 있다
- 높이가 1 감소하면: 앞으로 L칸이 같은 높이여야 경사로를 놓을 수 있다
- 높이 차이가 2 이상이면 불가능
핵심 아이디어: 오르막과 내리막을 별도로 처리하며, 경사로 겹침은 카운트를 0으로 초기화하여 방지한다.
코드
package ASP_study.day299;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day283BOJ14890경사로구현 {
static int N, L, CNT;
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());
}
}
CNT = 0;
for (int i = 0; i < N; i++) {
check(map[i]);
}
for (int i = 0; i < N; i++) {
int temp[] = new int[N];
for (int j = 0; j < N; j++) {
temp[j] = map[j][i];
}
check(temp);
}
System.out.println(CNT);
}
private static void check(int[] map) {
int f = map[0];
boolean flag = false;
for (int i = 0; i < N; i++) {
if (map[i] != f) {
flag = true;
break;
}
}
if (!flag) {
CNT++;
return;
}
int cnt = 0;
for (int i = 0; i < N; i++) {
if (map[i] == f)
cnt++;
else if (map[i] == f + 1) {
if (cnt >= L)
cnt = 1;
else
return;
} else if (map[i] == f - 1) {
if (i + L - 1 < N) {
for (int j = i; j < i + L; j++) {
if (map[j] != f - 1)
return;
}
i += (L - 1);
cnt = 0;
} else
return;
} else
return;
f = map[i];
}
CNT++;
}
}복잡도
- 시간: O(N²)
- 공간: O(N²)