[백준(Python/Java)] 14890_경사로

https://www.acmicpc.net/problem/14890

14890번: 경사로

 

문제를 해석을 잘못해서 엄청나게 복잡한 코드를 생각했었는데요. 처음에 이 문제를 봤을 때는 "가로로 설치한 경사로와 세로로 설치한 경사로가 겹치면 어떻게 하지?"에 대한 처리를 엄청 고민했습니다. 하지만 이 문제는 가로와 세로에 설치한 경사로를 따로 구분해서 푸는 문제이기 때문에 위와 같은 상황은 고려하지 않아도 되는 것이었죠.

 

따라서 이 문제는 매우 간단해집니다.

 

주어진 이차원 배열의 모든 행과 열을 탐색해보면서 해당 라인에 경사로를 설치해서 통과할 수 있는지를 판단해주면 됩니다. 따라서 기본적인 탐색에 드는 시간은 O(2*N)이면 충분합니다. 그리고 각 라인을 통과할 수 있는지 확인하는 로직에서 O(N) 시간이 소요되죠. 따라서 O(N^2) 시간복잡도 안에 충분히 해결할 수 있습니다.

 

"경사로를 설치해서 통과할 수 있는가?"를 판단하기 위한 로직도 그리 복잡하지 않습니다. 

• 만약 연속된 지점의 높이 차이가 2 이상이면 바로 실패합니다.
• 다음 지점이 현재지점보다 1만큼 높다면 1) 그 이전의 L만큼 구간이 동일한 높이를 가지는지, 2) 경사로를 놓으면 범위를 초과하지 않는지, 3) 경사로가 이미 설치된 곳은 아닌지를 판단합니다.
• 마찬가지로 다음 지점이 현재지점보다 1만큼 낮다면 1) 그 이후의 L만큼 구간이 동일한 높이를 가지는지, 2) 경사로를 놓으면 범위를 초과하지 않는지, 3) 경사로가 이미 설치된 곳은 아닌지를 판단합니다.

이를 코드로 구현하면 아래와 같습니다. *파이썬 주석에 설명한 내용이 자바 코드에도 그대로 적용됩니다.

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline

def isValidWay(line, graph):
    used = [False] * n # 경사로 건설 여부를 위한 리스트
    row = graph[line] # 현재 확인할 길 
    for i in range(n-1):
        # 높이가 다른 곳 발견        
        if row[i] != row[i+1]:
            # 높이가 2차이 이상 나면 실패
            if abs(row[i] - row[i+1]) >= 2:
                return False
            else:
                # 높은 곳에서 낮은 곳이면 그 이후를 관찰
                if row[i] == row[i+1] + 1:
                    # 순서대로 범위 초과, 지그재그, 이미 경사로 설치 확인
                    if i + l >= n: return False
                    if len(set(row[i+1:i+1+l])) != 1: return False
                    if any(used[i+1:i+1+l]): return False
                    for j in range(i+1, i+l+1):
                        used[j] = True
                # 낮은 곳에서 높은 곳이면 그 이전을 관찰
                elif row[i] == row[i+1] - 1:
                    if (i+1) - l < 0 : return False
                    if len(set(row[i+1-l:i+1])) != 1: return False
                    if any(used[i+1-l:i+1]): return False
                    for j in range(i+1-l, i+1):
                        used[j] = True

    return True

n, l = map(int, input().split())
row_graph = [list(map(int, input().split())) for _ in range(n)] # 행 탐색을 위한 그래프
col_graph = list(zip(*row_graph)) # 열 탐색을 위한 그래프
answer = 0

for line in range(n):
    if isValidWay(line, row_graph):
        answer += 1
    if isValidWay(line, col_graph):
        answer += 1
print(answer)

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.IntStream;

import static java.lang.Math.abs;

public class B_14890 {
    static int n, l;
    static int[][] row_graph, col_graph;
    static int answer;

    public static int[][] getTransposedGraph(int[][] origin){
        col_graph = new int[n][n];
        for(int i = 0; i < origin.length; i++){
            for(int j = 0; j < origin.length; j++){
                col_graph[i][j] = origin[j][i];
            }
        }
        return col_graph;
    }

    public static boolean isValidWay(int line, int[][] graph){
        boolean[] used = new boolean[n];
        int[] row = graph[line];
        for(int i = 0; i < n-1; i++){
            if(row[i] != row[i+1]) {
                // 높이가 2 차이 이상이면 실패
                if (abs(row[i] - row[i + 1]) >= 2) return false;

                // 높은 곳에서 낮은 곳이면 그 이후 관찰
                if (row[i] == row[i + 1] + 1) {
                    // 순서대로 범위, 지그재그, 기존 경사로 존재 확인
                    if (i + l >= n) return false;
                    Set<Integer> temp = new HashSet<>();
                    for (int j = i + 1; j < i + l + 1; j++) {
                        temp.add(row[j]);
                        if (used[j]) return false;
                    }
                    if(temp.size() > 1) return false;
                    for (int j = 0; j < i + l + 1; j++) {
                        used[j] = true;
                    }
                }
                // 낮은 곳에서 높은 곳이면 그 이전을 관찰
                else {
                    if(i+1-l < 0) return false;
                    Set<Integer> temp = new HashSet<>();
                    for(int j = i+1-l; j < i+1; j++){
                        temp.add(row[j]);
                        if(used[j]) return false;
                    }
                    if(temp.size() > 1) return false;
                    for(int j = i+1-l; j < i+1; j++){
                        used[j] = true;
                    }
                }
            }
        }
        return true;
    }

    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());

        row_graph = new int[n][n];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                row_graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        col_graph = getTransposedGraph(row_graph);

        for(int i = 0; i < n; i++){
            if(isValidWay(i, row_graph)) answer++;
            if(isValidWay(i, col_graph)) answer++;
        }
        System.out.println(answer);

    }
}