[Python] 백준 14890번 문제 풀이 - 경사로

문제 링크

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

문제 이해

N X N의 맵에서 다음과 같은 길을 만들수 있습니다. 맵의 행과 열이므로 총 2N 개의 길을 만들수 있는 것입니다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 합니다.

 

하지만 높이가 같지 않더라도 지나갈 수 있는 방법이 있는데요, 이 문제의 이름인 경사로를 놓는 것입니다.

경사로를 놓는 조건은 다음과 같은데요

• 경사로는 바닥과 평행하게 붙어있어야 한다.
• 낮은 칸과 높은 칸의 차이가 2이상이지 않아야 한다.
• 경사로의 길이보다 바닥의 길이가 작지 않아야 한다.

글자만 보고는 이해가 어려웠는데요 그림을 보며 이해할 수 있었습니다.

경사로는 세로 길이가 1, 가로 길이는 L인 직각삼각형 모양이였고, 아래의 두번째 그림처럼 바닥으로부터 떨어져 있으면 불가능하고, 아래의 세번째 그림처럼 겹치는 상황이 발생하면 안됩니다.

 

그리고 만약에 시작부터 끝까지 경사로를 두고 이동할 수 있다면 끝에서 시작까지 이동하는 것도 가능합니다.

그래서 반대 케이스는 딱히 생각하지 않아도 됐습니다.

아이디어

저는 경사로를 둘 수 있는 경우와 없는 경우를 4가지로 나누어서 길이 만들어지는 여부를 결정했습니다.

1. 이전 높이와 현재 높이의 차이가 2이상일 경우 길 만들기가 불가능하다.
2. 이전 높이와 현재 높이가 같을 경우 현재 지나온 길의 수를 저장하며 앞으로 한칸 이동한다.
3. 높이 차이가 1이고 이전 높이가 더 높을 때는 현재부터 어느정도까지 현재 높이와 같은 높이가 유지되는지 세고 경사로를 둘 수 있으면 경사로를 두고 같은 높이를 유지를 못했던(길이 끊겼던) 곳으로 이동한다.
4. 높이 차이가 1이고 이전 높이가 더 낮을 때는 지나온 길의 수를 확인하고 경사로를 둘 수 있는지 확인한다.

라는 아이디어를 떠올렸습니다.

 

이를 코드로 구현하는데는 좀 오래걸렸습니다. 아이디어를 코드로 구현 하는 능력이 아직 부족한 듯 합니다.

 

구현을 위해 아이디어를 구체화 했는데요,

우선 행과 열을 쭉 뽑아서 배열로 만들어서 함수 내부에 넣은 후

이게 길인지 아닌지 판단해서 맞다면 결과에 +1 하는 로직을 생각했습니다.

함수 내부의 로직은 다음과 같습니다.

1. 이전과 현재의 높이차이가 2이상이면 함수를 종료한다.
2. 이전과 현재의 높이가 같으면 진행한다.
3. 이전 높이가 현재의 높이보다 더 낮으면 여태까지 온 거리를 보고 경사로보다 작다면 함수를 종료하고, 아니라면 경사로를 높고 다음 위치로 이동해서 높이와 현재 온 길이를 1로 초기화 하고 진행한다.
4. 이전 높이가 현재의 높이보다 더 높으면 현재~길이 끊길때(높이가 다를때)까지의 길이를 재고 경사로보다 같거나 크면 경사로를 두고 남는길이를 이전 길이에 추가하고 길이 끝나는 부분으로 이동하고 함수를 진행한다.
5. 함수의 마지막에 다다랐다면 길이 만들어졌다고 판단하여 정답에 +1을 한다.

시간복잡도

이 아이디어의 시간복잡도는 O(n^3) 까지 나옵니다.

 

함수 내부는 1차원 배열을 받아 순회하는 것이라 O(n) 밖에 되지 않지만

행을 배열로 만드는 것은 O(n)이라 함수까지 돌면 O(n^2)이 되고

열을 배열로 만드는 것은 O(n^2)이라 함수까지 돌면 O(n^3)이 됩니다.

 

하지만 n은 최대가 100이기 때문에 가능합니다.

코드 구현

그래서 이 아이디어를 코드로 구현하면 다음과 같습니다.

import sys
input = sys.stdin.readline

n, l = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

answer = 0

def find_road(arr):
    global answer
    prev_height = arr[0]
    prev_cnt = 1

    i = 1
    while i < n:
        if abs(prev_height - arr[i]) > 1: # 차이가 2이상 일때
            return # 함수 종료
        elif prev_height == arr[i]: # 같을 때
            prev_cnt += 1 # 온 길 거리 +1
            i += 1  # 다음 값으로 진행
        elif prev_height > arr[i]: # 이전 높이가 더 높을 때
            # 같은 높이가 얼마나 이어지는지 확인
            next_cnt = 0 #
            for j in range(i, n):
                if arr[i] == arr[j]:
                    next_cnt += 1
                else:
                    break
            # 이어진 길이 경사로보다 크다면
            if next_cnt >= l:
                prev_height = arr[i] # 높이 최신화
                i+= next_cnt # 길이 끝나는 부분 다음으로 이동
                prev_cnt = next_cnt -l # 남는길이를 이전길이에 추가
            else:
                return
        elif prev_height < arr[i]: # 이전 높이가 더 낮을 때
            if prev_cnt >= l: # 이어진 길이 경사로보다 크다면 경사로 세우고 다음 높이로 이동 
                prev_height = arr[i] 
                prev_cnt = 1
                i += 1
            else:
                return
    
    # 끝에 도달했을 때 길이 만들어졌다고 생각하고 결과 + 1
    answer += 1

# 행 구하기
for row in graph:
    find_road(row)

# 열 구하기
for i in range(n):
    temp = []
    for j in range(n):
        temp.append(graph[j][i])
    find_road(temp)

print(answer)

새로 배웠던 부분

함수내의 반복문에 while을 쓴 이유는 for 구문 내부에서 i += 1을 사용할 때 인덱스가 증가하지 않았습니다.

 

파이썬에서 for 루프를 돌 때 인덱스가 증가하지 않는 이유는

미리 정해진 시퀀스를 순회하기 때문입니다.

미리 정해진 시퀀스가 뭐냐면 리스트나 range()가 반환하는 값들인데

arr [1,2,3] 이라면

(1,2,3)을 만들어두고 i는 이 시퀀스를 하나씩 할당하는 거고

range(5) 라면

(0,1,2,3,4)를 만들어두고 i가 이 시퀀스를 하나씩 할당해서 반복문이 돌아가기 때문에

밑의 조건문에서 아무리 i += 1 을 해봐야 할당될 것은 정해져 있기 때문에 인덱스가 증가하지 않았던 것이였습니다.