백준 14890번. 경사로 (Java, Python)

Problem

• 문제 링크

지도의 크기와 높이가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 문제입니다.

Solution

문제 특성상 코드가 굉장히 지저분하게 나올 수밖에 없다고 생각합니다.

우선 이 길이 맞는지 확인하는 canGo(x, y, d) 메소드를 만들었습니다.

시작 x, 시작 y, 그리고 가로 세로 여부를 판단하는 d 를 파라미터로 받습니다.

2차원으로 되어 있는 지도에서 길 하나만을 체크하는 것이기 때문에 height 라는 1차원 배열에 옮겨담았습니다.

그리고 visited 배열을 사용하였는데, 경사로를 중복으로 놓는 상황을 방지하기 위해서 만들었습니다.

height 배열을 1 ~ n-1 까지 돌면서 확인합니다.

1. 높이가 같으면 패스
2. 높이 차이가 2 이상이면 false
3. 내려가야 되는 경우
4. 올라가야 되는 경우

이렇게 4가지 경우를 만들어서 예외처리를 하였습니다.

내려가야 하는 경우는 다음 인덱스부터 앞으로 길이 L 만큼

올라가야 하는 경우는 현재 인덱스부터 뒤로 길이 L 만큼

경사로를 놓을 땅이 있는지 확인합니다.

1. 경사로 놓는 범위가 지도를 벗어나거나 j >= n
2. 경사로 놓는 땅의 높이가 다르거나 height[i+1] != height[j] or height[i] != height[j]
3. 이미 다른 경사로가 놓여있는 경우 visited[j] == true

위 세가지 경우 중에 하나라도 만족하면 false 를 return 합니다.

만약 위에 세 조건에 걸리지 않고 무사히 for 문을 돌면 끝까지 도착했다는 뜻이므로 true 를 return 합니다.

x 가 0 이며 세로로 가는 길 또는 y 가 0 이며 가로로 가는 길 모두 확인하며 카운트를 해준 뒤에 출력해주면 됩니다.

Java Code

import java.io.*;
import java.util.*;
 
class Main {
    static int stoi(String s) { return Integer.parseInt(s); }
 
    static int n;
    static int L;
    static int[][] map;
    static int count = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        L = stoi(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] = stoi(st.nextToken());
        }
 
        // 풀이 시작
        for (int i=0; i<n; i++) {
            if (canGo(i, 0, 0)) 
                count++;
            
            if (canGo(0, i, 1)) 
                count++;
        }
 
        System.out.println(count);
    }
 
    // 한 줄이 경사로인지 확인 d = 0 이면 행검사, d = 1 이면 열검사
    static boolean canGo(int x, int y, int d) {
        int[] height = new int[n];
        boolean[] visited = new boolean[n];     // 경사로가 이미 놓여있는지 체크
 
        // 알아보기 쉽게 height 배열에 옮기기
        for (int i=0; i<n; i++) {
            height[i] = (d == 0) ? map[x][y+i] : map[x+i][y];
        }
 
        for (int i=0; i<n-1; i++) {
            // 높이가 같으면 패스
            if (height[i] == height[i+1]) {
                continue;
            }
            
            if (Math.abs(height[i] - height[i+1]) > 1) {
                return false;
            }
 
            // 내려가야되는 경우
            if (height[i] - 1 == height[i+1]) {
                for (int j=i+1; j<=i+L; j++) {
                    // j가 범위를 벗어나거나 높이가 다르거나 이미 경사로가 있는 경우
                    if (j >= n || height[i+1] != height[j] || visited[j] == true) {
                        return false;
                    } 
                    visited[j] = true;
                }
            }
            // 올라가야되는 경우
            else if (height[i] + 1 == height[i+1]) {
                for (int j=i; j>i-L; j--) {
                    if (j < 0 || height[i] != height[j] || visited[j] == true) {
                        return false;
                    }
                    visited[j] = true;
                }
            }            
        }
 
        return true;
    }
}

Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
N = L = 0
arr = []
 
def canGoPath(heights):
    current = heights[0]
    visited = [False for i in range(N)]
 
    for i, height in enumerate(heights):
        ## 높이가 똑같으면 그냥 진행
        if current == height:
            continue
 
        ## 높은 곳으로 이동
        ## 지금까지 이동한 거리가 L보다 크거나 같으면 이동가능
        elif current + 1 == height:
            for j in range(i-1, i-1-L, -1):
                if j < 0 or current != heights[j] or visited[j] == True:
                    return False
                visited[j] = True
            current = height
 
        ## 낮은 곳으로 이동
        ## 앞으로 이동할 곳에서 L만큼 같은 거리가 있으면 가능
        elif current - 1 == height:
            for j in range(i, i+L):
                if j >= N or current - 1 != heights[j] or visited[j] == True:
                    return False
                visited[j] = True
            current = height
        
        ## 높이 차이가 1 이상이면 불가능
        else:
            return False
    
    return True
 
 
def solve():
    count = 0
    for i in range(N):
        if canGoPath(arr[i]):
            count += 1
 
    for j in range(N):
        path = []
        for i in range(N):
            path.append(arr[i][j])
        
        if canGoPath(path):
            count += 1
    
    print(count)
 
if __name__ == '__main__':
    N, L = map(int, sys.stdin.readline().split())
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    solve()