[SWEA] 모의 SW 역량테스트 4014번 활주로 건설 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

SW Expert Academy

[문제] 

[Fig. 1] 과 같은 N * N 크기의 절벽지대에 활주로를 건설하려고 한다.

각 셀의 숫자는 그 지형의 높이를 의미한다.

활주로를 [Fig. 2] 와 같이 가로 또는 세로 방향으로 건설할 수 있는 가능성을 확인하려고 한다.

활주로는 높이가 동일한 구간에서 건설이 가능하다.

높이가 다른 구간의 경우 활주로가 끊어지기 때문에 [Fig. 3] 과 같은 경사로를 설치해야만 활주로를 건설 할 수 있다.

경사로는 길이가 X 이고, 높이는 1 이다.

경사로는 높이 차이가 1 이고 낮은 지형의 높이가 동일하게 경사로의 길이만큼 연속되는 곳에 설치 할 수 있다.

예를 들어 [Fig. 4] 는 길이가 2 이고 높이가 1 인 경사로를 설치하는 예를 보여준다.

경사로의 길이 X 와 절벽지대의 높이 정보가 주어질 때,

활주로를 건설할 수 있는 경우의 수를 계산하는 프로그램을 작성하라.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,

그 다음 줄부터 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 크기인 N 과 경사로의 길이 X 가 주어진다.

다음 N 개의 줄에는 N * N 크기의 지형 정보가 주어진다.

[출력]

테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t" 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )

정답은 활주로를 건설할 수 있는 경우의 수이다.

 

 

---

[풀이]

1. 행 또는 열이 0인 경우에만 탐색을 하면 모든 경우를 탐색할 수 있다.

2. 탐색을 하는 도중 불가능한 경우가 발생한다면 멈춘다.

3. 불가능한 경우 없이 끝까지 탐색을 하면 카운트를 증가시켜준다.

[접근]

1. BFS로 완전 탐색을 하려고 생각함. (BFS가 아니라 결국 그냥 비교)

2. 시작부터 직선으로만 이동을 할 수 있으며, 마지막 지점까지 도달을 한다면 활주로를 생성할 수 있다는 것이다.

3. 시작 지점 (행 또는 열이 0)인 경우만 탐색을 한다.

4. 각 상황에 맞춰서 조건을 주고 불가능한 부분을 처리한다.

[코드]

package swet;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_test_4014 {
	static int T;
	static int n;
	static int x;
	static int[][] map;
	static int count;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			n = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());

			// 전체 초기화
			map = new int[n][n];
			count = 0;

			// 값 입력받기
			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++) {
					if (i == 0) { // 행이 0일때 탐색
						rowsearch(i, j);
					}
					if (j == 0) { // 열이 0일때 탐색
						colSearch(i, j);
					}
				}
			}
			System.out.println("#" + t + " " + count);
		}
	}

	public static void rowsearch(int r, int c) {
		int length = 1;
		int height = map[r][c];

		if (r == 0) {
			for (int i = 1; i < n; i++) {
				if (height - map[i][c] == 0) { // 높이가 같다면
					length++;
				}
				else if (height - map[i][c] == 1) { // 다음지점의 높이가 1 낮다면
					if (n - i < x) { // 남아있는 길이가 x보다 작다면 이후에 다 같은 높이가 나와도 경사로 생성이 불가능
						return;
					}
					else {
						for (int j = 1; j < x; j++) {
							if (height - map[++i][c] != 1)
								return;
						}
					}
					height = map[i][c]; // 높이를 바꿔준다
					length = 0; // 길이를 초기화 해준다
				}
				else if (height - map[i][c] == -1) { // 다음 지점의 높이가 1 높다면
					if (length >= x) { // 경사로를 설치할 수 있는 길이가 충분하다면
						height = map[i][c];
						length = 1;
					}
					else
						return;
				}
				else // 나머지는 경사로 생성 불가
					return;
			}
//			System.out.println("r일때 r : " + r + " c : " + c);
			count++;
		}	
	}

	public static void colSearch(int r, int c) {
		int length = 1;
		int height = map[r][c];

		if (c == 0) {
			for (int i = 1; i < n; i++) 
				if (height - map[r][i] == 0) { // 높이가 같다면
					length++;
				}
				else if (height - map[r][i] == 1) { // 다음지점의 높이가 1 낮다면
					if (n - i < x) { // 남아있는 길이가 x보다 작다면 이후에 다 같은 높이가 나와도 경사로 생성이 불가능
						return;
					}
					else {
						for (int j = 1; j < x; j++) {
							if (height - map[r][++i] != 1)
								return;
						}
					}
					height = map[r][i]; // 높이를 바꿔준다
					length = 0; // 길이를 초기화 해준다
				}
				else if (height - map[r][i] == -1) { // 다음 지점의 높이가 1 높다면
					if (length >= x) { // 경사로를 설치할 수 있는 길이가 충분하다면
						height = map[r][i];
						length = 1;
					}
					else
						return;
				}
				else // 나머지는 경사로 생성 불가
					return;
		}
//		System.out.println("c일때, r : " + r + " c : " + c);
		count++;
	}
}

[실수]

1. 탐색을 하는 도중 현재 높이보다 작은 경우가 왔을 때 따로 처리를 해주지 않아 값이 잘못 출력 됨