백준 14890번 : 경사로 [Java]

문제 탐색하기

문제는 가로와 세로 방향으로 길을 지날 수 있는지를 구해야 한다. 

• 경사로가 있거나 높이가 같을 때만 지날 수 있고
• 경사로는 더 낮은 높이의 칸의 길이가 L일 때만 놓을 수 있다.
• 경사로는 겹치거나, 높이 차이가 1이 아니거나 하면 놓을 수 없게 된다

위의 조건을 토대로 시간복잡도를 구해보면 결국 모든 칸을 2번씩은 방문해야한다 (가로, 세로) 이를 통하여 시간 복잡도를 구해보면 O(N ^ 2)이 되므로 시간안에 통과할 수 있을 것이다.

 

코드 설계하기

1. 입력을 처리하고 2차원 배열을 통해서 지도의 각 높이를 받아오도록 한다.
2. 경사로를 가로와 세로로 나누어 처리한다.
3. 가로와 세로 각각에서 아래의 경우에 대한 처리를 코드로 구현한다.
   1. 높이가 같을 때
   2. 높이 차이가 1 이상일 때
   3. 내리막길 / 오르막길 설치
4. 모든 가능한 경로를 더하여 출력한다.

풀이

import java.util.*;
import java.io.*;

public class Main {
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

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

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		N = fr.nextInt();
		L = fr.nextInt();

		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = fr.nextInt();
			}
		}

		int result = 0;

		// 가로 방향 체크
		for (int i = 0; i < N; i++) {
			if (canPass(map[i])) result++;
		}

		// 세로 방향 체크
		for (int i = 0; i < N; i++) {
			int[] col = new int[N];
			for (int j = 0; j < N; j++) {
				col[j] = map[j][i];
			}
			if (canPass(col)) result++;
		}

		System.out.println(result);
	}

	static boolean canPass(int[] line) {
		boolean[] built = new boolean[N];

		for (int i = 0; i < N - 1; i++) {
			if (line[i] == line[i + 1]) continue; // 높이 같으면 패스

			if (Math.abs(line[i] - line[i + 1]) > 1) return false; // 높이 차이가 1보다 크면 불가능

			if (line[i] > line[i + 1]) { // 내리막길 설치
				int height = line[i + 1];
				for (int j = i + 1; j <= i + L; j++) {
					if (j >= N || line[j] != height || built[j]) return false;
					built[j] = true;
				}
			} else { // 오르막길 설치
				int height = line[i];
				for (int j = i; j > i - L; j--) {
					if (j < 0 || line[j] != height || built[j]) return false;
					built[j] = true;
				}
			}
		}
		return true;
	}
}