본문 바로가기
알고리즘 풀이/백준

[백준 14890] 경사로(python)

by char_lie 2023. 4. 29.
반응형

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

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

경사로 문제

요구 조건에 맞게 경사로를 놓아서 지나갈 수 있는지 횟수 체크하는 구현 문제

📌 문제 접근 포인트

1. 문제 요구사항을 잘 따져주자. 요구사항이 많아서 헷갈릴 수 있다.
2. 가로 방향과 세로 방향을 모두 따져줘야 하고, 가로와 세로 둘 다 같은 방식으로 탐색을 하면 되니 함수를 만들어줘서 구성해 보자.
3. 요구 조건에 맞게 차이가 1보다 큰 경우와 왼쪽, 오른쪽이 더 클 경우로 나눠서, 각각 경사로를 설치해서 체크할 수 있도록 구성해 보자..
4. 요구 사항대로 부합한 개수를 구하면 완성

 

⚙ 내가 푼 정답 코드

# 조건 1 : 경사로를 놓아서 지나가는 길을 만들 수 있음
# 조건 2 : 경사로는 높이가 항상 1이고 길이는 L
# 조건 3-1 : 경사로는 낮은칸에 놓이고, L개의 연손된 칸에 경사로 바닥이 모두 접해야함
# 조건 3-2 : 낮은 칸과 높은 칸의 높이 차이는 1
# 조건 3-3 : 경사로를 놓을 낮은 칸의 높이는 모두 같아야하며 L개의 칸이 연속적
# 조건 4-1 : 경사로를 놓인곳에 또놓으면 x
# 조건 4-2 : 경사로 범위를 벗어나면 안됨
# 조건 4-3 : 낮은 곳의 높이가 모두 같지 않은 경우
def find(ways):
    visited = [False]*N
    for i in range(1,N):
        if abs(ways[i] - ways[i-1]) > 1: # 조건 2
            return False
        
        if ways[i-1] > ways[i] : # 왼쪽 지점이 더 클 때
            for j in range(L): # 경사로 크기까지
                if i + j >= N or ways[i] != ways[i+j] or visited[i+j]: # 경사로가 밖을 벗어나거나, 길이가 다르거나, 이미 설치했다면 (조건 4)
                    return False
                if ways[i] == ways[i+j]: # 좌우 높이가 같으면 (조건 1) 
                    visited[i+j] = True # 경사로 놓자 
                    
        elif ways[i-1] < ways[i] : # 오른쪽 지점이 더 클 때
            for j in range(L):
                if i - j - 1 < 0 or ways[i-1] != ways[i - j - 1] or visited[i - j - 1]: # 경사로가 밖을 벗어나거나, 길이가 다르거나, 이미 설치했다면 (조건 4)
                    return False
                if ways[i-1] == ways[i-j-1]: #조건 1
                    visited[i-j-1] = True
    return True

import sys
N, L = map(int, sys.stdin.readline().split())
way = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
cross = list(zip(*way)) 
result = 0
for i in range(N) :
    if find(way[i]): # 가로
        result += 1
    if find(cross[i]): #세로
        result += 1
print(result)
반응형

댓글