BOJ 14890. 경사로 (Python)

주어진 조건대로 경사로를 이용하거나 그냥 통행할 수 있는 길을 구하라

문제의 설명 때문에 이해하는데에 오래 걸렸던 문제이다.

• N x N 행렬이 존재할 때, 각 행, 열을 지나 갈 수 있는지 여부를 판단한다
• 각 셀에 적힌 수 (10 보다 작거나 같은 자연수) 는 높이를 뜻하며, 셀 간의 높이가 1 차이일 때 경사로를 설치 할 수 있다.
• 경사로는 L의 밑변을 가지며, 경사로는 겹쳐질 수 없다. (아래 그림 과 같이)

행렬이 주어질 때, 지나 갈 수 잇는 길의 개수를 구하는 프로그램을 작성하시오

각 행, 열을 판단해야하는 문제인데 겹치지 않는 경사로에 현혹되어서, 한 행에 경사로가 설치되면, 그 행을 지나는 열의 경로에는 경사로를 못 넣는 것으로 생각해서 너무 어려웠다. 하지만 그냥 각 행과 열을 따로 생각하는 문제...(급격히 쉬워짐)

각 행과 열을 생각했을 때, 고려해야하는 부분은 이것이다.

1. 인덱스 0부터 시작하여서 높이가 다른 셀을 만났을 때, 낮은 곳이 L 보다 같거나 큰 개수로 이어져야한다.
2. 높아졌을 떄는, 낮은 것이 얼마나 이어졌는지 기록한다.
3. 낮아졌을 때는, 이후에 L 이상으로 길이가 같은지 확인한다.
4. 매번 경사로가 겹치지는 않는지 확인한다.

일단 높아지건 낮아지건 블럭이 1차이가 나야 의미가 있다.

또 가장 신경 썻던 부분은, 통행 가능 한지 였으므로 못찾는다면 바로 0을 return 하도록 했다.

높아질때는, 받침보다 길게 이어지는지와, 그 구간에 경사로가 있는지를 확인한다

if abs(prev - current) == 1:
      # 1 높아질 때
      if prev + 1 == current:
      	# 만약 받침보다 길게 이어진다면
        if count >= L:
        # slope에 경사로 저장 부분을 확인.
          if slope[i-L:i] != [0] * L:
            return 0
          # 경사로를 두고 저장
          slope[i-L:i] = [1] * L
        else:
          return 0
        

낮아 질때는, 그 다음 구간이 범위 (N)을 넘어서는지, 그리고 경사로가 겹치지는 않는지, 해당구간이 연속되는지 여부를 봤다.

elif prev - 1 == current:
        # 범위를 벗어나지 않는지 확인
        if i + L <= N:
          # 겹치는 경사로가 있는지 확인
          if line[i: i+L] == [current] * L:
            slope[i: i+L] = [1] * L
          else:
            return 0
        else:
          return 0

따라서 전체 풀이는 아래와 같다.

def check_if(N, L, line):
  prev = 0
  count = 0
  slope = [0] * N
  available = True
  # 인덱스 0부터 순회함
  for i in range(N):
    current = line[i]
    # 첫칸이거나, 이어질때 prev를 두고 갯수를 기록한다.
    if not prev or prev == current:
      prev = current
      count += 1
      continue
    # 더 높은 블럭이 1차이 나야함
    if abs(prev - current) == 1:
      # 1 높아질 때
      if prev + 1 == current:
      	# 만약 받침보다 길게 이어진다면
        if count >= L:
        # slope에 경사로 저장 부분을 확인.
          if slope[i-L:i] != [0] * L:
            return 0
          # 경사로를 두고 저장
          slope[i-L:i] = [1] * L
        else:
          return 0
      # 1 낮아질 때
      elif prev - 1 == current:
        # 범위를 벗어나지 않는지 확인
        if i + L <= N:
          # 겹치는 경사로가 있는지 확인
          if line[i: i+L] == [current] * L:
            slope[i: i+L] = [1] * L
          else:
            return 0
        else:
          return 0
      # 경사로 만들고 다시 진행
      prev = current
      count = 1
    # 차이가 1보다 크면 못건넘
    else:
      return 0
  return 1
  
  
def sol():
  result = 0
  for i in range(N):
    result += check_if(N, L, grid[i])
  
  for j in range(N):
    line = [grid[x][j] for x in range(N)]
    result += check_if(N, L, line)

  print(result)

sol()