[백준14890&파이썬] 여러 실패케이스를 한번에 처리할 수 있는지 고민해보자

# 문제

백준 14890 경사로 파이썬 풀이

14890번: 경사로

# 코드

import sys

def print2D(arr) :
  for i in arr :
    print(i)



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

for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

# print2D(board)

# flat한지 확인해야 한다.
  # Flat하다면 길이 된다.
# flat하지 않다면
  # 경사로를 놓을 수 있다.
    # 높이차이가 2 이상이라면 경사로를 놓을 수 없다.
    # 범위를 벗어나는지 확인해야한다.



# 경사로를 놓는 후보지의 공간을 찾아보자.
# 경사로가 이미 깔린 지점인지 확인하자
ground = [[False] * N for _ in range(N)]
resultA = 0
for row in range(N) :
  cur = board[row][0]
  flag = True # 해당 줄이 길이 되는지 확인해주는 flag
  for col in range(1,N) :
    if abs(cur-board[row][col]) >= 2 : # 2차이 이상이 나는 곳은 애초에 구할 수가 없다.
      flag = False
      break

    elif abs(cur-board[row][col]) == 1 : # 1차이가 나는 경우, 후보공간을 찾아볼 필요가 있을듯
      # 경사로를 놓을 수 있는 후보공간의 크기가 적합한지 판단해야함
      if cur > board[row][col] : # 2 > 1
        tr = row; tc = col
        target = cur - 1
        diff = 1
      else : # 1 < 2
        tr = row; tc = col-1
        target = cur
        diff = -1
      # 공통으로 돌리기 가능 함.
      flatSize = 0
      candidate = list()
      while flatSize < L:
        # 범위 이내이면서, 경사로가 설치되었던 곳이 아니고, 평평한 곳이라면
        if (0 <= tr < N and 0 <= tc < N) and not ground[tr][tc] and board[tr][tc] == target:
          candidate.append((tr, tc))
          flatSize += 1
          tc += diff
        else:
          break
      # 최종적으로 경사로를 놓을 수 있는 곳이라면 경사로를 놓아준다.
      # print(f"row : {row}, candidate : {candidate}")
      if flatSize == L:
        for item in candidate:
          ground[item[0]][item[1]] = True
        cur -= diff
      else:
        # 경사로를 놓을 수 없는 곳이다!
        flag = False
        break
    else : # 차이가 안나는 경우
      cur = board[row][col] # 현재 높이로 업데이트 해준다.

  if flag :
    resultA +=1
    # print("HIT row : ", row)

# 아랫길
ground = [[False] * N for _ in range(N)]
resultB = 0
for col in range(N) :
  cur = board[0][col]
  flag = True # 해당 줄이 길이 되는지 확인해주는 flag
  for row in range(1,N) :
    if abs(cur-board[row][col]) >= 2 : # 2차이 이상이 나는 곳은 애초에 구할 수가 없다.
      flag = False
      break

    elif abs(cur-board[row][col]) == 1 : # 1차이가 나는 경우, 후보공간을 찾아볼 필요가 있을듯
      # 경사로를 놓을 수 있는 후보공간의 크기가 적합한지 판단해야함
      if cur > board[row][col] : # 2 > 1
        tr = row; tc = col
        target = cur - 1
        diff = 1
      else : # 1 < 2
        tr = row-1; tc = col
        target = cur
        diff = -1
      # 공통으로 돌리기 가능 함.
      flatSize = 0
      candidate = list()
      while flatSize < L:
        # 범위 이내이면서, 경사로가 설치되었던 곳이 아니고, 평평한 곳이라면
        if (0 <= tr < N and 0 <= tc < N) and not ground[tr][tc] and board[tr][tc] == target:
          candidate.append((tr, tc))
          flatSize += 1
          tr += diff
        else:
          break
      # 최종적으로 경사로를 놓을 수 있는 곳이라면 경사로를 놓아준다.
      # print(f"row : {col}, candidate : {candidate}")
      if flatSize == L:
        for item in candidate:
          ground[item[0]][item[1]] = True
        cur -= diff
      else:
        # 경사로를 놓을 수 없는 곳이다!
        flag = False
        break
    else : # 차이가 안나는 경우
      cur = board[row][col] # 현재 높이로 업데이트 해준다.

  if flag :
    resultB +=1
    # print("HIT col : ", col)

print(resultA+resultB)

# 풀이

• 코드가 길어보이지만 row단위로 탐색한번과 col단위 탐색 한번으로 똑같은 코드 방향만 바꿔서 두번하는 거다.

• 경사로를 놓을 수 없는 경우가 위와 같이 4가지가 있다.
• 일단 볼것도 없이 2개이상 차이가 나면 경사로를 놓을 수 없다. 그런 경우를 만나게 되면 해당 길에 대한 탐색을 끝내버린다.
• 경사로를 놓게 되는 경우는 아주 크게 따져보면 두가지가 된다.

• cur의 높이(근데 before라고 이름을 짓는게 맞았을 듯)가 현재 보게되는 board[row][col]과 비교했을때 아래와 같이 나눌 수 있다.
  • cur > board[row][col] ==> CASE 1 
  • cur < board[row][col] ==> CASE 2 
• 그리고 경사로는 크기 L에 맞게 놓을 수 있다. CASE1인 경우는 현재위치로부터 앞으로 이동하면서 경사로를 놓고, CASE2인 경우는 현재위치로부터 뒤로 이동하면서 경사로를 놓는다.
  • 그리고는 ground변수로 하여금 경사로를 추가한 곳에 대한 방문기록을 해놓는다.
• 이렇게 두개의 CASE1과 CASE2로 나눈 후, 경사로를 놓을 수 있을때 경사로를 무조건적으로 놓아버리게 되면 장점이 생긴다.
  • 바로 경사로를 놓을 수 없는 4가지 경우 중 2,3,4번째가 한번에 체킹이 된다.

      flatSize = 0
      candidate = list()
      while flatSize < L:
        # 범위 이내이면서, 경사로가 설치되었던 곳이 아니고, 평평한 곳이라면
        if (0 <= tr < N and 0 <= tc < N) and not ground[tr][tc] and board[tr][tc] == target:
          candidate.append((tr, tc))
          flatSize += 1
          tc += diff
        else:
          break

• 왜냐하면 위 조건을 검색할때, 범위를 나가는지확인한 후, ground[tr][tc]로 이미 깔린 곳인지 확인하기 때문이다.
• 그래서 범위상 경사로를 놓을 수 있는 곳이어도, 이미 경사로를 놓음으로서 생기는 놓을 수 없는 경우 2,3,4경우가 확인이 된다.