[백준] 경사로

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

14890번: 경사로

구현 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

NxN의 지도가 주어지고, 이 지도의 가로줄과 세로줄을 "길" 이라고 정의합니다. 이 때, 길들은 모두 높이가 같거나 경사로를 놓을 수 있는 경우에만 지나갈 수 있을 때, 경사로의 길이와, 지도가 주어질 때, 길중에서 지나갈 수 있는 길의 수를 구하는 것이 문제입니다. 

 

문제의 조건이 조금 있으니 위의 링크에서 실제로 예시와 문제를 같이 읽어보는 것이 정확합니다.

 

<Solution>

구현 문제입니다. 우선 available 이라는 함수를 만들어 길의 정보가 들어오면 해당하는 길을 지나가는 것이 가능한지 불가능 한지 return할 수 있도록 하였습니다.

def available(road, L): # input road = [3,2,1,2,3,1,2...]

 

이제 이 함수에 대해 조금 더 자세하게 설명하면, 크게 아래와 같은 알고리즘으로 구성됩니다.

1. 해당 함수는 매번 같은 높이의 블록이 몇개 연속하여 있는지를 기록하고 있습니다.
2. 만약 높이가 2이상 차이가 난다면 즉시 False로 return 합니다.
3. 높은 곳에서 낮은 곳으로 (높이 차이 : 1) 가는 경우, flag를 설정해주고, 지속적으로 체크하다 가능한 경우 경사로를 놓고 flag를 해제 합니다.
4. 낮은 곳에서 높은 곳으로 (높이 차이 : 1) 가는 경우, 이전에 연속한 블록의 수를 참조하여, 경사로를 놓을 수 있는지 판단합니다.
5. 이전의 블록과 지금 블록이 같다면 그냥 연속한 블록수를 하나 늘려줍니다.
6. 만약 Flag가 설정 되어 있다면 지속적으로 for loop의 마지막에 현재 flag를 해제(경사로를 놓을수 있는지) 를 체크합니다.(3번과정의 추가설명)

문제에서 조금 생각하여야 하는 부분은 높은 곳에서 낮은 곳으로 가는 경우와, 낮은 곳에서 높은 곳으로 진행하는 경우를 분리하여 생각 하여야 하는 것입니다. (경사로는 낮은 블록에만 놓을 수 있기 때문)

 

이러한 알고리즘을 실제로 구현 하면 되고 코드는 아래와 같습니다.

import sys

N, L = list(map(int,sys.stdin.readline().rstrip().split()))
graph = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)]

def available(road, L): # input road = [3,2,1,2,3,1,2...]
    # get points where height changes
    tmp = road[0]
    cnt = 1 # count same height
    hl_flag = 0

    for r in road[1:]:
        if abs(tmp - r) >= 2:
            return False
        elif tmp - r == 1: # high to low
            if hl_flag == 1:
                return False
            cnt = 1
            tmp = r
            hl_flag = 1
        elif r - tmp == 1: # low to high
            if hl_flag == 1:
                return False
            if cnt >= L:
                cnt = 1
                tmp = r
            else:
                return False
        else:
            cnt += 1
        
        # check (hight to low)
        if hl_flag == 1:
            if cnt == L:
                hl_flag = 0 
                cnt = 0

    if hl_flag == 0:
        return True
    else:
        return False

ans = 0
for row in graph:
    if available(row, L):
        ans += 1
        # print(row)

for col in zip(*graph):
    if available(col, L):
        ans += 1
        # print(col)
print(ans)