[Baekjoon] 14890번 : 경사로 (Python, 구현)

[Baekjoon] 14890번 : 경사로 (Python, 구현)

 

목차

 

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

14890번: 경사로

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 84ms / 코드 길이 917B

 

통과 기준은 크게 3가지이다.

1) 내 앞에 있는 path index의 값과의 높이 차가 없을 때 (path[k-1] == path[k])

2) 내 앞에 있는 path index의 값보다 1 낮을 때

3) 내 앞에 있는 path index의 값보다 1 높을 때

 

2와 3의 경우는 추가로 길이 l의 경사로를 놓을 수 있는지 확인해야 한다.

만약 경사로가 겹치거나 길이를 넘어서는 경우 예외 처리를 진행해야 한다.(여기서는 flag bool 사용) 

 

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

for i in range(n):
    for j in range(n):
        arr[i].append(graph[j][i])

arr = graph + arr
cnt = 0
flag = False
for path in arr:
    visit = [0]*n
    for k in range(1, n):
        if path[k-1] == path[k]:
            continue
        elif path[k-1] - path[k] == 1:
            if sum(path[k:k+l]) == path[k]*l and sum(visit[k:k+l]) == 0:
                visit[k:k+l] = [1]*l
            else:
                flag = True
                break
        elif path[k] - path[k-1] == 1:
            if sum(path[k-l:k]) == path[k-1]*l and sum(visit[k-l:k]) == 0:
                visit[k-l:k] = [1]*l
            else:
                flag = True
                break
        else:
            flag = True
            break
    if flag:
        flag = False
    else:
        cnt += 1
print(cnt)

 

방법 2 - 메모리 30840KB / 시간 76ms / 코드 길이 1003B

 

방법 1과 동일한 아이디어를 가진다.

다만 함수형으로 만든다는 차이가 있다.

 

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

def check_line(line):
    for i in range(1, n):
        if abs(line[i] - line[i - 1]) > 1:
            return False
        if line[i - 1] - line[i] == 1:
            for j in range(l):
                if i + j >= n or line[i] != line[i + j] or visit[i + j]:
                    return False
                if line[i] == line[i + j]:
                    visit[i + j] = 1
        elif line[i] - line[i - 1] == 1:
            for j in range(l):
                if i - j - 1 < 0 or line[i - 1] != line[i - j - 1] or visit[i - j - 1]:
                    return False
                if line[i - 1] == line[i - j - 1]:
                    visit[i - j - 1] = 1
    return True

for i in range(n):
    visit = [0] * n
    if check_line([graph[i][j] for j in range(n)]):
        cnt += 1

for j in range(n):
    visit = [0] * n
    if check_line([graph[i][j] for i in range(n)]):
        cnt += 1

print(cnt)