문제

BOJ 14890, 경사로

핵심

• 입력의 크기가 $100$이라 구현에 초점을 맞춘다.
• 지도에서 행과 열을 기준으로 지나갈 수 있는 길을 파악해야 한다. 만약 길 높낮이가 다르다면 경사로를 설치할 수 있다. 경사로는 일정한 길이가 있기에 문제에서 주어진 만큼 평평한 땅이 존재해야 한다. 아래 경사로 설치 기준을 참고하자.
  
• 지나갈 수 있는 길은 파란색, 지나갈 수 없다면 파란색 길이다.
  
• 행에서 지나갈 수 있는 길을 판단하고, 열에서 지나갈 수 있는 길인지 판단하기 위해 로직을 수정하기 보다는 지도를 90도 회전시켜 하나의 판단 로직으로 지나갈 수 있는 행과 열을 판단하도록 하였다.
• 기본적인 구현
  1. 길의 높이가 같다면, 평평한 부분의 길이를 구한다.
  2. 길이 높아졌다면, 지나온 길에 경사로를 설치해야 하므로 지나온 길의 갯수가 경사로의 길이보다 같거나 커야 한다.
  3. 길이 낮아졌다면, 길이 낮아진 곳에 경사로를 설치해야 하므로 길이 낮아진 곳부터 시작하는 평평한 길이가 경사로 길이보다 같거나 커야 한다.
• 길이 낮아졌을 때 경사로를 설치했다면 평평한 부분으로 세면 안 된다. 경사로를 또 설치할 수 없기 때문이다. 따라서 bridge배열을 두어 경사로를 설치한 부분을 제외한 곳만 평평한 길이에 추가했다.
• 구현 하고 나서 맞왜틀? 한 부분이 있었는데 순수하게 높이 차이가 1이라고 생각했던 점이다. 만약 높이 차이가 1보다 크다면 경사로를 설치할 수 있어도 지나갈 수 없다.

개선

코드

시간복잡도

• $O(n^2)$

C++

#include <iostream>
using namespace std;

int n, l;
int map[104][104];
int ans = 0;
void rotate() {
	int tmp[104][104];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			tmp[i][j] = map[i][j];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			map[j][n - i - 1] = tmp[i][j];
	}
}

void checkRow() {
	for (int row = 0; row < n; ++row) {
		int flat = 0;
		int prev = map[row][0];
		bool isBridge[104] = {};
		for (int col = 0; col < n; ++col) {
			if (abs(map[row][col] - prev) > 1)
				break;
			if (prev > map[row][col]) {
				int nCol = col;
				int nFlat = 0;
				int nH = map[row][col];
				while (nCol < n) { // 길이 낮아진 곳부터 평평한 길이를 잰다.
					if (nFlat == l || nH != map[row][nCol])
						break;
					isBridge[nCol] = true;
					++nFlat;
					++nCol;	
					nH = map[row][col];
				}
				if (nFlat < l)
					break;
				flat = 0;
			} else if (prev < map[row][col]) {
				if (flat < l)
					break;
				flat = 0;
			}
			if (!isBridge[col])
				++flat;
			prev = map[row][col];
			if (col == n - 1)
				++ans;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> l;	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			cin >> map[i][j];
	}
	checkRow();
	rotate();
	checkRow();
	cout << ans;
}

Java

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

public class Main {
    static int n, l;
    static int[][] map = new int[104][104];
    static int ans = 0;
    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());
        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());
        }
        checkRow();
        rotate();
        checkRow();
        System.out.println(ans);
        br.close();
    }
    
    static void checkRow() {
        for (int row = 0; row < n; ++row) {
            int flat = 0;
            int prev = map[row][0];
            boolean[] isBridge = new boolean[n];
            for (int col = 0; col < n; ++col) {
                if (Math.abs(map[row][col] - prev) > 1)
                    break;
                if (prev > map[row][col]) {
                    int nCol = col;
                    int nFlat = 0;
                    int nH = map[row][col];
                    while (nCol < n) {
                        if (nFlat == l || nH != map[row][nCol])
                            break;
                        isBridge[nCol] = true;
                        ++nFlat;
                        ++nCol;
                    }
                    if (nFlat < l)
                        break;
                    flat = 0;
                } else if (prev < map[row][col]) {
                    if (flat < l)
                        break;
                    flat = 0;
                }
                if (!isBridge[col])
                    ++flat;
                prev = map[row][col];
                if (col == n - 1)
                    ++ans;
            }
        }
    }

    static void rotate() {
        int[][] tmp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j)
                tmp[i][j] = map[i][j];
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j)
                map[j][n - i - 1] = tmp[i][j];
        }
    }
}