문제
[Fig. 1] 과 같은 N * N 크기의 절벽지대에 활주로를 건설하려고 한다.
각 셀의 숫자는 그 지형의 높이를 의미한다.
활주로를 [Fig. 2] 와 같이 가로 또는 세로 방향으로 건설할 수 있는 가능성을 확인하려고 한다.
활주로는 높이가 동일한 구간에서 건설이 가능하다.
높이가 다른 구간의 경우 활주로가 끊어지기 때문에 [Fig. 3] 과 같은 경사로를 설치해야만 활주로를 건설 할 수 있다.
경사로는 길이가 X 이고, 높이는 1 이다.
경사로는 높이 차이가 1 이고 낮은 지형의 높이가 동일하게 경사로의 길이만큼 연속되는 곳에 설치 할 수 있다.
예를 들어 [Fig. 4] 는 길이가 2 이고 높이가 1 인 경사로를 설치하는 예를 보여준다.
경사로의 길이 X 와 절벽지대의 높이 정보가 주어질 때,
활주로를 건설할 수 있는 경우의 수를 계산하는 프로그램을 작성하라.
[예시]
지도의 한 변의 크기 N 이 6, 경사로의 길이 X 가 2 일 때,
[Fig. 5] 와 같이 지형의 높이가 주어진 경우를 생각해 보자.
[Fig. 5] 의 지형 중 [ 3, 3, 3, 2, 1, 1 ] 의 경우 [Fig. 6] 과 같이 높이 2 인 구간이 경사로 길이보다 짧아서 활주로를 설치 할 수 없다.
[ 3, 3, 3, 2, 2, 1 ] 의 지형은 [Fig. 7] 과 같이 경사로를 지형 밖까지 설치해야 되기 때문에 활주로를 설치할 수 없다.
[ 2, 2, 3, 2, 2, 2 ] 지형과 [ 3, 3, 3, 2, 2, 2 ] 지형의 경우 아래 [Fig. 8-1], [Fig. 8-2] 와 같이 경사로를 설치하여 활주로를 건설할 수 있다.
[Fig. 5] 와 같은 지형에 활주로를 건설하는 방법은
아래 [Fig. 9] 와 같이 총 7 가지 ( 가로 방향 3 가지, 세로 방향 4 가지 ) 경우가 있다.
즉, 예제에 대한 정답은 7 이 된다
[제약사항]
-
시간제한 : 최대 50 개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3 초
-
N 의 크기는 6 이상 20 이하의 정수이다. ( 6 ≤ N ≤ 20 )
-
경사로의 높이는 항상 1 이고, 길이 X 는 2 이상 4 이하의 정수이다. ( 2 ≤ X ≤ 4 )
-
지형의 높이는 1 이상 6 이하의 정수이다.
-
동일한 셀에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.
( 아래 [Fig. 10] 과 같은 경우는 경사로를 설치하여 활주로를 연결 할 수 없다. )
-
경사로는 세워서 사용할 수 없다. ( [Fig. 11] 참고 )
[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,
그 다음 줄부터 T 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 크기인 N 과 경사로의 길이 X 가 주어진다.
다음 N 개의 줄에는 N * N 크기의 지형 정보가 주어진다.
[출력]
테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t" 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )
정답은 활주로를 건설할 수 있는 경우의 수이다.
문제 파악하기
처음에는 활주로를 몇개 설치할 수 있는지에 대한 문제인 줄 알고 가로와 세로가 겹쳤을 때를 체크하기 위한 visited 배열을 따로 만들어야겠구나, DFS로 접근하면 되겠다 라는 생각을 했었는데,
문제를 다시 보면 다음과 같다.
위의 사진처럼 예제의 정답이 7이라고 한 것을 보아
각각의 줄마다 독립적으로 활주로를 설립할 수 없는 것이 있다면 out이고, 경사 진 곳에 대하여 활주로를 전부 설치할 수만 있다면 정답으로 셀 수 있는 것이었다.
그래서 접근한 방식은 각각의 행과 열마다 활주로를 건설할 수 없는 경우가 있는지 확인만하고, 한 칸이라도 활주로를 건설할 수 없으면 out 하면 되는 문제
문제풀이1
각각의 행과 열에 대하여 독립적으로 검증을 해야하기 때문에
isPossible이라는 메서드로 따로 분리하여 접근
활주로가 건설 되지 못하는 데에 중요한 것은 연속된 두 곳의 높이 차이
int diff = arr[i] - arr[i-1]로 접근
불가능 조건 1
둘의 높이 차이가 2이상이면 불가능(오르막길이든 내리막길이든)
if (Math.abs(diff) > 1) {
return false;
}이제 diff에 대하여 케이스를 나눌 수 있다
-> 오르막길 / 내리막길 / 평지 이렇게 각각 케이스를 나눠서 불가능한 조건에 대하여 false를 반환해주면 된다
불가능 조건 2 (오르막길)
if (diff == 1) {
if (cnt >= X) {
cnt = 1; // 초기화
} else {
return false;
}
}평지
평지일 경우에는 별 상관 없이 계속 세어주면 된다.
if (diff == 0) {
cnt++;
}불가능 조건 3 (내리막길)
내리막길이라면 그 다음에서 평지가 (X-1)개 만큼 존재해야한다.
그래서 앞으로의 cnt에서 -X이라는 제약을 줌으로써 해당 값이 0이상이 될때까지 평지를 계속 마주하지 못하면 return false가 되도록 조건문을 작성한다.
else { // diff == -1
if (cnt >= 0) {
cnt = -X + 1;
} else {
return false;
}
}그리고 최종적으로 cnt >= 0 이라면 true를 반환하고 아니라면 false를 반환하도록 함으로써 -X 제약을 가진 cnt가 중간에 끊기면 out되도록 체크해준다.
isPossible 전체 코드
public static boolean isPossible(int[] arr) {
// 사용될 연속된 길이
int cnt = 1;
for (int i = 1; i < N; i++) {
// 차이를 기준으로 경우 나누기
int diff = arr[i] - arr[i-1];
if (Math.abs(diff) > 1) {
return false;
}
// 1. 오르막길을 마주함
if (diff == 1) {
if (cnt >= X) {
cnt = 1; // 초기화
} else {
return false;
}
}
// 2. 평지를 마주함
else if (diff == 0) {
cnt++; // 계속 연속된 길이 세면 됨
}
// 3. 내리막길을 마주함
else { // diff == -1
if (cnt >= 0) {
cnt = -X + 1; // -X만큼의 제약을 가지고 for문 반복
} else {
// 계속 음수
return false;
}
}
}
return cnt >= 0;
전체 코드
이제 이걸 각각의 세로와 가로에 대하여 독립적으로 검증해주면 끝이다.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int N, X;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
String[] nx = br.readLine().split(" ");
N = Integer.parseInt(nx[0]);
X = Integer.parseInt(nx[1]);
int[][] plane = new int[N][N];
for (int i = 0; i < N; i++) {
String[] line = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
plane[i][j] = Integer.parseInt(line[j]);
}
}
int answer = 0;
// 가로를 기준으로 검증
for (int i = 0; i < N; i++) {
if (isPossible(plane[i])) {
answer++;
}
}
// 세로를 기준으로 검증
for (int i = 0 ; i<N; i++) {
int[] col = new int[N];
for (int j = 0; j < N; j++) {
col[j] = plane[j][i]; // 세로만
}
if (isPossible(col)) {
answer++;
}
}
System.out.println("#" + tc + " " + answer);
}
}
// 한 줄 마다 실행
public static boolean isPossible(int[] arr) {
// 사용될 연속된 길이
int cnt = 1;
for (int i = 1; i < N; i++) {
// 차이를 기준으로 경우 나누기
int diff = arr[i] - arr[i-1];
if (Math.abs(diff) > 1) {
return false;
}
// 1. 오르막길을 마주함
if (diff == 1) {
if (cnt >= X) {
cnt = 1; // 초기화
} else {
return false;
}
}
// 2. 평지를 마주함
else if (diff == 0) {
cnt++; // 계속 연속된 길이 세면 됨
}
// 3. 내리막길을 마주함
else { // diff == -1
if (cnt >= 0) {
cnt = -X + 1; // -X만큼의 제약을 가지고 for문 반복
} else {
// 계속 음수
return false;
}
}
}
return cnt >= 0;
}
}문제풀이2
한 줄에 대하여 시작~끝 까지의 검증을 하는 dfs 실행
시작 ~ 끝 으로 가는 도중에 out 조건을 마주치면 종료
public class Solution {
static int N, X;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
String[] nx = br.readLine().split(" ");
N = Integer.parseInt(nx[0]);
X = Integer.parseInt(nx[1]);
int[][] plane = new int[N][N];
for (int i = 0; i < N; i++) {
String[] line = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
plane[i][j] = Integer.parseInt(line[j]);
}
}
int answer = 0;
// 가로를 기준으로 검증
for (int i = 0; i < N; i++) {
int[] used = new int[N];
if (dfs(plane[i], 0, used)) {
answer++;
}
}
// 세로를 기준으로 검증
for (int i = 0 ; i<N; i++) {
int[] col = new int[N];
int[] used = new int[N];
for (int j = 0; j < N; j++) {
col[j] = plane[j][i]; // 세로만
}
if (dfs(col, 0, used)) {
answer++;
}
}
System.out.println("#" + tc + " " + answer);
}
}
private static boolean dfs(int[] arr, int pos, int[] used) {
if (pos == N -1) {
return true; // 끝까지 감
}
int curr = arr[pos];
int next = arr[pos+1];
// 1. 같은 높이 -> 다음 위치로 이동하면 됨
if (curr == next) { // 평지
return dfs(arr, pos+1, used);
}
// 2. 다음이 1 낮음 -> 이후의 X칸 되는지 확인
if (curr - next == 1) {
for (int i = pos +1; i <= pos + X; i++) { // X번만큼 검사
// 인덱스 아웃과 이미 지었는지와 계속 동일 길이인지 확인
if (i >= N || arr[i] != next || used[i] == 1) {
return false;
}
}
for (int i = pos +1; i <= pos + X; i++) { // X번만큼 검사
used[i] = 1;
}
// 한 번에 X 칸 건너뜀 (검사 통과된 애들)
return dfs(arr, pos + X, used);
}
// 3. 다음이 1 높음 -> 이전이 X칸 되는지 확인
if (next - curr == 1){
for (int i = pos; i > pos -X; i--) {
// 인덱스 아웃과 이미 지었는지와 계속 동일 길이인지 확인
if (i < 0 || arr[i] != curr || used[i] ==1) {
return false;
}
}
for (int i = pos; i > pos -X; i--) {
used[i] = 1;
}
return dfs(arr, pos + 1, used);
}
// 4. 높이 차이가 2이상이면 불가능
return false;
}
}
