[14890] 경사로

😲 문제

출처
크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.


오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
아래와 같은 경우에는 경사로를 놓을 수 없다.

경사로를 놓은 곳에 또 경사로를 놓는 경우
낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
경사로를 놓다가 범위를 벗어나는 경우

입력 
6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

출력
3

❗️ 문제 재정의

정리
행과 열을 따로 검사하여 총 지나갈 수 있는 길을 구해야한다.

1. 경사로는 두가지 종류가 있다.
   1. 현재 위치가 다음 위치보다 높은 경우
   2. 현재 위치가 다음 위치보다 낮은 경우
2. 한 번 설치한 경사로에 또 설치 불가능하다.
   1. 방문 배열을 만들어야 한다.
   2. 경사로의 조건에 하나라도 충족 안될 시 길이 아니다.
      1. 높이가 2 이상 차이가 날 경우
      2. 경사로를 놓은 곳에 또 경사로를 놓는 경우
      3. 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
      4. 경사로를 놓다가 범위를 벗어나는 경우

✔ 계획 수립

1. n, l을 입력으로 받기
2. nxn 행렬을 만들고 값을 입력받기
3. 한 행씩 방문 배열을 만든 후 한 행씩 검사하기
   1. 전부 다 같은 값이라면 +1
   2. 1 이상 차이가 나는 경우가 있다면 False
   3. 1만 차이가 나는 경우라면
      1. 현재 위치가 다음 위치보다 높은 경우
         1. 현재 위치 다음부터 l개 만큼의 범위 여유가 있는가?
         2. l개만큼의 칸이 높이가 같은지 검사
      2. 현재 위치가 다음 위치보다 낮은 경우
         1. 현재위치부터 l개만큼의 범위 여유가 있는가?
         2. l개만큼의 칸이 높이가 같은지 검사

👨🏻‍💻 문제 풀이

import sys
input = sys.stdin.readline
n, l = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

def check_road(line, n, l, visited):
    for i in range(n-1):
        if abs(line[i] - line[i+1]) >= 2: # 높이가 1 이상 차이나는 경우
            return False 
        if abs(line[i] - line[i + 1]) == 1: # 높이가 딱 1만 차이나는 경우
            if line[i] < line[i+1]: # 현재 위치가 다음 위치보다 더 낮은 경우
                # 충분한 범위가 있는가? 방문하지 않았는가?
                if i-l+1 >= 0:
                    for j in range(i, i-l, -1):
                        if line[j] != line[i] or visited[j]:
                            return False
                    for j in range(i, i-l, -1):
                        visited[j] = True
                else:
                    return False
            else:
                # 현재 위치가 다음 위치보다 높은 경우
                if i+l < n:
                    for j in range(i+1, i+l+1):
                        if line[j] != line[i+1] or visited[j]:
                            return False
                    for j in range(i+1, i+l+1):
                        visited[j] = True
                else:
                    return False
    return True
          
road = 0
for line in graph:
    visited = [False] * n
    if len(set(line)) == 1 or check_road(line, n, l, visited):
        road += 1
        
graph_transposed = list(zip(*graph)) # 전치행렬
for line in graph_transposed:
    visited = [False] * n
    if len(set(line)) == 1 or check_road(line, n, l, visited):
        road += 1
print(road)

😅 회고

하나의 행과 하나의 열은 각각 독립적이라는 사실을 몰랐었다. 행에 설치한 경사로가 열에게도 영향을 주는줄 알았지만 아니였다. 문제의 요지는 길로 만들 수 있는 행,열의 개수는 몇 개인가 였다..

if abs(line[i] - line[i + 1]) == 1: # 높이가 딱 1만 차이나는 경우
10번째 줄의 조건을 else:로만 놓아서 한참을 헤맸다.
높이가 1이 아니라 딱 같은 경우가 들어가면 False가 반환되기에 문제인 상황이였다. 높이가 1인 상황에서만 경사로를 설치해야 하기에 문제의 조건을 좀 더 상기시켰다면 충분히 더 쉽게 해결 가능했다..

범위를 조심해서 풀면 된다.(인덱스 에러가 자주 발생했다..ㅠ)