[알고리즘 / 백준] 14890 - 경사로

www.acmicpc.net/problem/14890

14890번: 경사로

 

문제는 위와 같으며, 가로로 1줄, 세로로 1줄을 길이라고 하기 때문에 길이 될 수 있는 경우를 확인하는 경우는 2N 번이 됩니다. 1줄에 해당하는 높이 배열을 받아서 현 위치의 높이와 다음 위치의 높이를 비교하여 같은 경우, 낮은 경우, 높은 경우에 따라 그에 맞는 처리를 해주고 결과적으로 길이 되면 true 를 안되면 false 를 반환해서 길이 된 경우 길의 수를 증가시켜주고 모든 2N 번의 경우를 확인한 다음 길의 수를 출력해주면 됩니다.

 

현 위치의 높이와 다음 위치의 높이를 비교하여 처리하는 것은 다음과 같습니다.

 

1. 높이가 같은 경우

: 마지막 높이의 개수를 증가시키고 다음 위치를 확인하는 반복을 진행합니다.

 

2. 마지막 높이보다 다음 높이가 높아진 경우 (높이 차이 1)

: 다음 높이가 높아진 경우는 앞에 경사로를 세워야 하는데 이때 앞에 같은 위치의 높이가 L개만큼 있는지 확인합니다. 확인 방법은 마지막 높이의 개수를 가지고 있었기 때문에 이 개수가 L개보다 작은 경우는 경사로를 세울 수 없습니다. 따라서 이때는 결과를 false 로 하고 반복을 종료합니다.

  만약 L개보다 커서 경사로를 놓을 수 있는 경우는 다음 높이를 마지막 높이로 하고 마지막 높이의 수는 1로 수정한 뒤, 다음 위치를 확인하는 반복을 계속 수행합니다.

 

3. 마지막 높이보다 다음 높이가 낮아진 경우 (높이 차이 1)

: 다음 높이가 낮아지는 경우는 뒤로 경사로를 세워야하므로 뒤로 같은 높이의 위치가 L개만큼 존재하는지 확인합니다. 이때 뒤로 남은 위치의 개수가 L개보다 작은 경우는 경사로를 세울 수 없기 때문에 결과를 false 로 하고 반복을 종료합니다. 남은 위치의 개수가 L개보다 많은 경우는 L개만큼 반복하면서 높이가 다른지 확인하고 다르다면 결과를 false 로 하고 반복을 종료합니다. L개의 높이가 같은 위치가 존재하는 경우 경사로를 세울 수 있기 때문에 이때 다음 수를 마지막 수로 지정하고 이때 마지막 수의 개수를 0으로 한 뒤 다음으로 확인할 위치를 다음 위치 + L로 지정하고 남은 위치를 확인하는 반복을 마저 진행합니다.

 

4. 위 경우에 모두 해당하지 않는 경우 (높이 차이가 2이상)

: 경사로조차 놓을 수 없는 경우이므로 결과를 false 로 하고 반복을 종료합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


def find_path(p):
    answer = True
    last = p[0]  # 현재 위치의 높이 값 (초기 맨 처음 값)
    count = 1  # 현재 위치의 높이와 같은 위치의 개수

    cnt = 1
    while cnt < n:
        if last == p[cnt]:  # 현재 위치와 다음 위치가 같은 경우
            count += 1  # 같은 위치의 개수 증가
            cnt += 1
        elif p[cnt] - last == 1:  # 다음 위치의 높이가 높아진 경우
            if count < l:  # 지금까지 높이가 같은 위치의 수가 경사로를 세우기 위해 필요한 길이보다 작은 경우
                answer = False  # 경사로를 세울 수 없으므로 종료
                break

            last = p[cnt]  # 다음 위치의 높이를 마지막 높이로 저장하고
            count = 1  # 그 수를 1개로 초기화 한 뒤
            cnt += 1  # 다음 위치를 반복 확인
            continue
        elif last - p[cnt] == 1:  # 다음 위치의 높이가 낮아진 경우
            if n - cnt >= l:  # 남아있는 길이가 경사로를 세우기 위해 필요한 길이만큼 있는 경우
                for a in range(cnt + 1, cnt + l):  # 경사로 길이만큼 반복하면서
                    if p[cnt] != p[a]:  # 위치의 높이가 다른 경우
                        answer = False  # 반복을 종료
                        break
                if not answer:  # 더 이상 확인할 필요가 없기 때문에 종료
                    break

                cnt = cnt + l  # 다음 확인할 위치를 원래 다음 위치 + 경사로의 길이로 지정하고
                last = p[cnt - 1]  # 마지막 높이를 지정합니다.
                count = 0  # 이때 마지막 위치와 같은 위치 값의 개수를 0개로 지정합니다.
            else:  # 남아있는 길이가 경사로를 세우기 위해 필요한 길이보다 작은 경우
                answer = False  # 경사로를 세울 수 없기 때문에 종료
                break
        else:  # 위치의 높이 차이가 2이상 나는 경우 종료
            answer = False
            break

    return answer


n, l = map(int, stdin.readline().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, stdin.readline().split())))

path = 0  # 결과

for i in range(n):
    tmp = matrix[i]  # 가로로 놓인 길 확인
    if find_path(tmp):
        path += 1

    tmp = []
    for j in range(n):  # 세로로 확인할 길 저장
        tmp.append(matrix[j][i])

    if find_path(tmp):
        path += 1

print(path)

 

 

자바 코드는 다음과 같습니다.

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

public class Main {
    private static int n;
    private static int l;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        int path = 0;

        for (int i = 0; i < n; i++) {
            int[] tmp = map[i];  // 가로 길 확인
            if (findPath(tmp)) {
                path += 1;
            }

            tmp = new int[n];
            for (int j = 0; j < n; j++) {  // 세로 길 구하기
                tmp[j] = map[j][i];
            }

            if (findPath(tmp)) {  // 세로 길 확인
                path += 1;
            }
        }

        System.out.println(path);
    }

    private static boolean findPath(int[] map) {
        boolean answer = true;
        int last = map[0];
        int count = 1;

        int cnt = 1;
        while (cnt < n) {
            if (last == map[cnt]) {  // 마지막 확인 높이와 다음 높이가 같은 경우
                count += 1;  // 같은 높이 위치 개수 증가
                cnt += 1;
            } else if (map[cnt] - last == 1) {  // 다음 위치가 높아진 경우
                if (count < l) {  // 앞에 높이가 같은 위치가 L개 보다 적은 경우는 경사로를 세울 수 없으므로 종료
                    answer = false;
                    break;
                }

                last = map[cnt];  // 경사로를 세울 수 있는 경우 다음 위치의 높이를 마지막 확인 높이로 저장하고
                count = 1;  // 그 수를 1로 초기화
                cnt += 1;
            } else if (last - map[cnt] == 1) {  // 다음 위치가 낮아진 경우
                if (n - cnt >= l) {  // 뒤로 남은 위치의 개수가 경사로를 세울 수 있을 만큼의 개수라면
                    for (int i = cnt + 1; i < cnt + l; i++) {  // 경사로를 세우기 위해 필요한 위치만큼 확인하면서
                        if (map[cnt] != map[i]) {  // 높이가 달라지는 경우는 종료
                            answer = false;
                            break;
                        }
                    }

                    if (!answer) {
                        break;
                    }

                    cnt += l;  // 경사로를 세울 수 있다면 다음 확인할 위치를 지금 확인한 다음 위치 + 경사로의 길이로 지정하고
                    last = map[cnt - 1];  // 마지막 확인 높이를 낮아진 위치의 높이로 지정
                    count = 0;  // 낮아진 높이의 경우 이미 경사로를 세우는데 사용했으므로 0으로 초기화
                } else {  // 뒤로 남은 위치의 개수가 경사로를 세우기에 충분하지 않은 경우 종료
                    answer = false;
                    break;
                }
            } else {  // 위치의 높이 차이가 2이상인 경우 종료
                answer = false;
                break;
            }
        }

        return answer;
    }

}