알고리즘 문제 풀이

8 / 16

백준 14890 경사로 with Python

알고리즘

문제 링크


알고리즘

  • 구현

Tip

가로 행을 검사하는 함수를 만들고, 2차원 배열의 행과 열을 바꿔서(Transpose) 한 번 더 구한다. 이렇게 하면 세로 행 검사 코드를 따로 작성하지 않아도 된다.

res += road_cnt() # 가로 행 검사

# Transpose
for i in range(N):
    for j in range(i, N):
        _map[i][j], _map[j][i] = _map[j][i], _map[i][j]

res += road_cnt() # 가로 행 검사

풀이 과정

for loop으로 돌면서 해당 행이 지나갈 수 있는 길인지 판정한다.

행을 i, 열을 j로 놓고 j가 처음(0)부터 마지막 열(N)까지 무사히 이동하면 해당 행은 지나갈 수 있는 길이다. while loop으로 반복하면서 j를 마지막 열까지 이동시킨다. j가 다음 열로 이동할 수 있는지 판정하는 로직은 다음과 같다. (열 == 칸)

  1. 현재 칸과 다음 칸이 평행하다면 통과
  2. 현재 칸과 다음 칸의 높이 차가 2이상이면 길이 없음
  3. 다음 칸이 더 낮을 때 3-1. 경사로를 놓아도 범위를 벗어나는 경우 - 길이 없음 3-2. 경사로를 놓을 칸들의 높이가 모두 같을 경우 - 경사로를 놓을 수 있다. 경사로를 놓은 칸을 기록해놓는다(같은 칸에 경사로를 중복해서 놓는 것은 안되므로).
  4. 다음 칸이 더 높을 때 4-1. 경사로를 놓아도 범위를 벗어나는 경우 - 길이 없음 4-2. 경사로를 놓을 칸들의 높이가 모두 같고 & 칸들에 경사로가 이미 놓아져 있지 않을 경우 - 경사로를 놓을 수 있다. 경사로를 놓은 칸을 기록해놓는다.

이런식으로 모든 행을 검사하면 결과를 구할 수 있다.

전체 코드

import sys

input = sys.stdin.readline
N, L = map(int, input().split())

# 입력받은 2차원 리스트
_map = [list(map(int, input().split())) for _ in range(N)]

res = 0  # 결과값


# 모든 행을 for loop으로 돌면서 지나갈 수 있는 길의 개수를 구한다.
def road_cnt():
    cnt = 0  # 지나갈 수 있는 길의 개수

    for i in range(N):  # 행 검사
        row = _map[i]  # 원본 row
        copy_row = row.copy()  # 복사본 row (경사로를 놓은 칸을 저장)
        j = 0
        is_road = True  # 길이 있는지 없는지

        # j가 끝까지(N-1) 가면 길이 있다고 판정
        while j < N - 1:
            # 현재 칸과 다음 칸이 평행하다면 통과
            if row[j] == row[j + 1]:
                j += 1

            # 현재 칸과 다음 칸의 높이 차가 2이상이면 길이 없음
            elif abs(row[j] - row[j + 1]) > 1:
                is_road = False
                break

            # 다음 칸이 더 낮을 때
            elif row[j] > row[j + 1]:
                # 경사로를 놓아도 범위를 벗어나는 경우 - 길이 없음
                if j + L >= N:
                    is_road = False
                    break

                # 경사로를 놓을 칸들의 높이가 모두 같을 경우 경사로를 놓을 수 있다.
                # 경사로를 놓은 칸을 저장한다. (copy_row)
                if row[j + 1 : j + L + 1].count(row[j + 1]) == L:
                    for col in range(j + 1, j + L + 1):
                        copy_row[col] = -1
                    j += L
                else:
                    is_road = False
                    break

            # 다음 칸이 더 높을 때
            elif row[j] < row[j + 1]:
                # 경사로를 놓아도 범위를 벗어나는 경우 - 길이 없음
                if j + 1 - L < 0:
                    is_road = False
                    break

                # 경사로를 놓을 칸들의 높이가 모두 같을 경우
                # And
                # 그 자리에 이미 경사로가 놓여있지 않을 경우
                # 경사로를 놓을 수 있다.
                # 경사로를 놓은 칸을 저장한다. (copy_row)
                if (
                    row[j + 1 - L : j + 1].count(row[j]) == L
                    and copy_row[j + 1 - L : j + 1].count(-1) == 0
                ):
                    for col in range(j + 1 - L, j + 1):
                        copy_row[col] = -1
                    j += 1
                else:
                    is_road = False
                    break

        if is_road:
            cnt += 1

    return cnt


res += road_cnt()

# Transpose
# 행과 열을 바꿔서 한 번 더 진행
for i in range(N):
    for j in range(i, N):
        _map[i][j], _map[j][i] = _map[j][i], _map[i][j]

res += road_cnt()
print(res)