문제

BOJ 14890: 경사로 https://www.acmicpc.net/problem/14890

풀이

조건

• 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다.
• 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.
• 경사로는 높이가 항상 1이며, 길이는 L이다.
• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 수 없는 조건
  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우

풀이 순서

• 가로와 세로의 길을 체크했다.
• visited 배열을 사용해 경사로를 놓은 곳의 위치를 표시했다.
• check 함수를 사용해 경사로를 왼쪽으로 놓는 경우와 오른쪽으로 놓는 경우를 나눠 확인했다.

코드

Python

import sys

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

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

def check(line, L):
    # 경사로 생기는 곳 체크
    visited = [False for _ in range(N)]
    # 자리 차례로 탐색
    for i in range(0, N-1):
        # 바로 다음 위치의 높이가 같으면 continue
        if line[i] == line[i+1]:
            continue
        # 다음 위치의 높이 차이가 1 넘게 나면 False
        elif abs(line[i]-line[i+1]) > 1:
            return False
        # 현재 높이가 다음 높이 보다 높으면 오른쪽 높이가 같은지 체크
        elif line[i] > line[i+1]:
            temp = line[i+1] # 다음 높이
            for j in range(i+1, i+L+1):
                # 경사 길이가 범위 안이면
                if 0 <= j < N:
                    # 경사 놓을 위치의 높이가 하나라도 다르면
                    if temp != line[j]:
                        return False
                    # 높이는 다 같은데 이미 경사가 놓여진 곳이면
                    elif visited[j]:
                        return False
                    # 경사 놓기
                    visited[j] = True
                # 경사 길이가 범위 벗어나면
                else:
                    return False
        # 다음 높이가 현재 높이 보다 높으면 왼쪽 높이가 같은지 체크
        else:
            temp = line[i]
            for j in range(i, i-L, -1):
                # 경사 길이가 범위 안이면
                if 0 <= j < N:
                    # 경사 놓을 위치의 높이가 하나라도 다르면
                    if temp != line[j]:
                        return False
                    # 높이는 다 같은데 이미 경사가 놓여진 곳이면
                    elif visited[j]:
                        return False
                    # 경사 놓기
                    visited[j] = True
                # 경사 길이가 범위 벗어나면
                else:
                    return False
    return True

answer = 0
# 가로 길 체크
for i in board:
    if check(i, L):
        answer += 1

# 세로 길을 체크하기 위해 변환해서 넣어줌
for i in range(N):
    temp = []
    for j in range(N):
        temp.append(board[j][i])
    if check(temp, L):
        answer += 1

print(answer)

정리

• 경사를 놓은 위치를 체크할 배열을 사용하지 않아 해결하는 데 시간을 많이 썼다.
• 여러 조건을 체크하고 분기를 나누는 연습을 더 해야되겠다.