[백준] 14890. 경사로

[Gold III]

 

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

분류 : 구현

 

문제 요약

N x N 격자에서 가로 또는 세로로 길을 만들 수 있는지 판단하는 문제.
경사로는 높이차 1인 구간에만 길이 L 만큼 설치 가능하며, 겹칠 수 없음.

 

풀이

• 각 행과 열을 하나의 길로 보고 모두 확인 
• 길을 왼 -> 오, 위 -> 아래 이렇게 순차적으로 한 줄씩 탐색하면서 경사로를 놓을 수 있는지 판단함 
• 경우의 수를 모두 구해서 확인하면 됨  
  
  up: 오르막 경사로 가능 길이
  down: 내리막 경사로 가능 길이
  h: 현재 높이
1. 시작 시 오르막 경사로 가능 길이(up) +1
2. 같은 높이  
   • down == 0이면 up += 1 → 경사로 놓을 준비 가능
   • down != 0이면 내리막 도중인데 경사로 설치가 안 된 상태 → 불가능
3. 높이 + 1 
   • 앞쪽에 up >= L이면 경사로 설치 가능 → up = 1, down = 0, 높이 갱신
   • 아니면 → 불가능
4. 높이 -1 
   • down += 1, 그리고 down == L이면 경사로 설치 완료 → up = 0, down = 0, 높이 갱신
   • down < L이면 경사로 설치 도중 → 다음 칸도 봐야 함
   • 이전 칸들과 겹쳐선 안 되기 때문에 조건 체크 필요
5. 높이 +- 2 -> 불가능

 

시간 복잡도

O(N²) — 각 행/열마다 최대 N번 순회

 

코드

N, L = map(int, input().split())

M = [] # map 
for i in range(N):
    M.append(list(map(int, input().split())))

res = 0 # 가능한 길의 개수 


for i in range(N):
    up = 1
    down = 0
    h = M[i][0] # 맨 처음 열이 시작높이 
    for j in range(1,N):
        if M[i][j] == h :
            if down != 0 : # 한칸 아래가 있었다는 의미. 근데 경사로를 못놓기 때문에 break
                break 
            else : # down == 0 -> 내려가는게 없다.
                up += 1 # 경사로 가능 길이 + 1  
               # continue # 계속 옆으로 가면 됨 

        elif M[i][j] == h + 1 : 
            # up += 1
            if up >= L : 
                up = 1
                down = 0 # 높이 바뀌었기 때문에 초기화 
                h = M[i][j]
            else : break 
        elif M[i][j] == h - 1:
            down += 1
            if down >= L: # 경사로 둘수 있는 길이가 되면 
                up = 0
                down = 0
                h = M[i][j] # 내려감 
        else:
            break
    
        if j == N -1 and down == 0 : 
            res += 1 


for j in range(N):
    up = 1
    down = 0
    h = M[0][j] # 맨 처음 행이 시작높이 
    for i in range(1,N):
        if M[i][j] == h :
            if down != 0 : # 한칸 아래가 있었다는 의미. 근데 경사로를 못놓기 때문에 break
                break 
            else : # down == 0 -> 내려가는게 없다.
                up += 1 # 경사로 가능 길이 + 1  

        elif M[i][j] == h + 1 : 
            # up += 1
            if up >= L : 
                up = 1
                down = 0 # 높이 바뀌었기 때문에 초기화 
                h = M[i][j]
            else : break 
        elif M[i][j] == h - 1:
            down += 1
            if down >= L: # 경사로 둘수 있는 길이가 되면 
                up = 0
                down = 0
                h = M[i][j] # 내려감 

        else:
            break
        
        if i == N -1 and down == 0 : 
            res += 1
     
    
                
print(res)

 

회고

처음에 마지막 조건문 위치를 잘못 넣어 마지막 한칸에서 틀린 경우도 길을 만들 수 있다고 판단했었다. 

조건을 잘 확인하고 헷갈리면 중간 중간 확인하면서 꼼꼼하게 구현해야 겠다.

그리고 질문 게시판의 반례를 찾아보는 것도 좋지만, 실제 시험에서는 더 많은 예시를 제공하지 않기 때문에 직접 반례를 만들어 보는 과정도 필요하다고 생각되었다.