백준: 14890 경사로

문제

14890번: 경사로

 

문제 풀이

 NxN 지도가 주어지고 각각의 칸에 높이가 주어진다. 이 지도에서 지나갈 수 있는 길이 몇 개 인지 찾아 반환하는 문제이다. 여기서 길은 지도의 하나의 행 또는 열을 의미한다. 길을 지나갈 때 높이가 다른 경우 경사로를 설치하여 지나갈 수 있게 만들 수 있다. 단 경사로의 길이만큼 길이가 확보되지 않거나, 경사로를 설치할 수 없는 영역 또는 높이의 차가 2 이상이라면 설치할 수 없다.

 

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

 예제 입력 1의 경우 위의 그림과 같이 3개의 길을 지나갈 수 있다. 나머지 경우들은 경사로를 설치할 수 없어 지나갈 수 없다. 경사로 설치가 가능한지를 판단하기 위해서는 아래와 같은 경우를 판단하면 된다.

 

• 하나의 행, 열의 높이가 모두 같은 경우
• 하나의 행, 열에서 이전의 높이와 현재의 높이가 같은 경우
  • 경사로가 설치 가능한 길이를 판단하기 위해 카운트
• 경사 상승: 하나의 행, 열에서 현재 높이 - 이전의 높이는 1인 경우
  • 경사로가 설치가능한 길이(카운트)가 확보되었다면 계속 진행
  • 불가능하다면 중단
• 경사 하락: 하나의 행, 열에서 현재 높이 - 이전의 높이가 -1인 경우
  • 내려가는 경사로의 경우, 바로 이전에 경사 하락을 한 경우가 아니라면 카운트를 -L + 1로 변경.
  • -L + 1 부터 다시 카운트하여 현재 높이를 포함하여 경사로가 설치돼있는지 확인하기 위함
  • 불가능하다면 중단
• 위의 모든 경우가 아닌 경우, 조건을 만족하지 않으므로 중단
• 즉, 하나의 행, 열을 중단하지 않고 모두 탐색하고 카운트가 음수가 아니라면, 지나갈 수 있는 길을 의미함

 

코드

from sys import stdin
from collections import Counter


def passable(graph):
    answer = 0

    for i in range(n):
        if len(Counter(graph[i])) == 1:
            answer += 1
            continue

        cur_height = graph[i][0]
        cnt = 1
        for j in range(1, n):
            # 이전 높이와 현재 높이가 같으면
            if graph[i][j] == cur_height:
                cnt += 1
            # 이전 높이와 현재 높이가 차가 +1
            elif graph[i][j] - cur_height == 1:
                if cnt >= l:
                    cnt = 1
                else:
                    break
            # 이전 높이와 현재 높이의 차가 -1
            elif graph[i][j] - cur_height == -1:
                if cnt >= 0:
                    cnt = -l + 1
                else:
                    break
            else:
                break

            # 모든 경우를 통과한 경우, 현재 높이를 변경
            cur_height = graph[i][j]
        else:
            answer += 1 if cnt >= 0 else 0

    return answer


if __name__ == '__main__':
    n, l = map(int, stdin.readline().split())
    horizontal = [list(map(int, stdin.readline().split())) for _ in range(n)]
    vertical = list(zip(*horizontal))
    print(passable(horizontal) + passable(vertical))

 가로, 세로에 따라 별도로 처리하기 귀찮아서, 처음에 입력되는 값을 `zip`을 활용하여 행열을 전치시켰다.😉