4014 활주로 탐색

 

 

BF로 완전탐색해도 문제가 없었다.

두번정도 수정 후, 제출시 40번에서 fail이 발생했다. 

아래의 반례에서 fail이 되었는데, 2 1 1 1 2  를 처리할 때 활주로 건설 후, dupCnt를 1로 초기화 한것이 문제였다.

이를 0으로 변경 후, Pass 됨.

다른 풀이를 찾아보니 검사를 dfs로 하는 방법도 있다.

 

1
6 2
2 1 2 1 2 3
2 1 2 1 2 1
2 1 2 1 2 3
2 1 2 1 2 3
3 5 6 5 5 5
2 1 1 1 2 2

 

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Solution {

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

	private static boolean DBG = false;
	private static int ans;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		StringTokenizer st = null;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			X = 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());
				}
			}
			ans = 0;

			for (int i = 0; i < N; i++) {
				int dupCnt = 1;
				boolean result = true;
				boolean isDownHill = false;

				for (int j = 1; j < N; j++) {
					if (map[i][j - 1] == map[i][j]) {
						++dupCnt;
						// 내리막에서 활주로를 건설하고 카운트 초기화
						if (isDownHill && dupCnt == X) {
							isDownHill = false;
							dupCnt = 0;
							//j++;
						}

					} else if (map[i][j - 1] - map[i][j] == -1 ) {
						// 오르막을 만난 경우, 카운트가 X보다 작을 경우, 활주로 건설 불가
						if (dupCnt >= X) {
							dupCnt = 1;
							
						} else {
							result = false;
							break;
						}
					} else if (map[i][j - 1] - map[i][j] == 1) {
						// 내리막을 발견하면 카운트를 초기화하고 내리막을 표시
						if (!isDownHill) {
							isDownHill = true;
							dupCnt = 1;						
						} else {
							// 내리막에서 활주로 건설 없이 다시 내리막을 만난 경우
							result = false;
							break;
						}
					} else {
						result = false;
						break;
					}
				}

				if (!isDownHill && result)
					ans++;

			}

			for (int i = 0; i < N; i++) {
				int dupCnt = 1;
				boolean result = true;
				boolean isDownHill = false;

				for (int j = 1; j < N; j++) {
					if (map[j - 1][i] == map[j][i]) {
						++dupCnt;
						// 내리막에서 활주로를 건설하고 카운트 초기화
						if (isDownHill && dupCnt == X) {
							isDownHill = false;
							dupCnt = 0;
							//j++;
						}

					} else if (map[j - 1][i] - map[j][i] == -1) {
						// 오르막을 만난 경우, 카운트가 X보다 작을 경우, 활주로 건설 불가
						if (dupCnt >= X) {
							dupCnt = 1;
						} else {
							result = false;
							break;
						}
					} else if (map[j - 1][i] - map[j][i] == 1) {
						// 내리막을 발견하면 카운트를 초기화하고 내리막을 표시
						if (!isDownHill) {
							isDownHill = true;
							dupCnt = 1;
						} else {
							// 내리막에서 활주로 건설 없이 다시 내리막을 만난 경우
							result = false;
							break;
						}
					} else {
						result = false;
						break;
					}
				}

				if (!isDownHill && result)
					ans++;

			}

			System.out.println("#" + test_case + " " + ans);
		}
	}

}