meatsby.github.io

BOJ 14890 - 경사로

3 min read

풀이

경사로를 배치하여 행이나 열을 처음부터 끝까지 통과가능 여부를 찾는 문제이다.

행과 열을 모두 확인해야하기 때문에 zip() 을 통해 column 들을 row 로 변환시켜 graph 에 extend 해주었다.

각 row 들을 확인하면서 아래 명시된 조건들 중 하나도 부합하지 않을 경우 통과 불가능한 길로 판단하여 False 를 배정한다.

우선 경사로를 배치가능한지 판단하기 위하여,

  1. 경사로를 이미 배치했었는지

  2. 경사로를 배치할 공간이 충분한지

  3. 경사로가 끝나는 지점의 높이가 맞는지

총 세가지의 조건을 걸어 경사로를 통해 올라갈 경우와 내려갈 경우를 나눠서 선언했다.

두 조건 모두 부합하지 않을 경우 바로 지나갈 수 있는지를 판단한 뒤, 그 또한 부합하지 않을 경우 통과 불가능한 길로 판단하여 False 를 배정한다.

이후 isTrue 를 사용해 모든 조건을 배합하여 반복문을 탈출한 경로일 경우 ans += 1 을 해주고 모든 row 에 대한 반복이 끝나면 ans 를 출력해준다.

소스코드

# 경사로
import sys
input = sys.stdin.readline
 
n, l = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
graph.extend(list(zip(*graph)))
ans = 0
 
for line in graph:
    isTrue = True
    canImp = [True for _ in range(n)]  # 경사로 배치 가능?
    i = 0
    while True:
        # print(i, end="")
        if i >= n-1:  # 범위내에서
            break
        elif canImp[i] and i < n-l and len(set(line[i:i+l])) == 1 and line[i]+1 == line[i+l]:  # 경사로를 통해 올라갈 경우
            for k in range(i, i+l):
                canImp[k] = False
            i += l
        elif canImp[i+1] and i < n-l and len(set(line[i+1:i+l+1])) == 1 and line[i]-1 == line[i+l]:  # 경사로를 통해 내려갈 경우
            for k in range(i+1, i+l+1):
                canImp[k] = False
            i += l
        elif i < n-1 and line[i] == line[i+1]:  # 같은 높이일 경우
            i += 1
        else:
            isTrue = False
            break
    if isTrue:
        ans += 1
    # print(isTrue)
 
print(ans)

References

Graph View