14890번 – 경사로

1

문제

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

풀이

코드

from copy import deepcopy
n, l = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
height, width, RIGHT, LEFT, 경사로 = (n, n, 1, -1, '#')
record = [[0]*width for _ in range(height)]

def 보드돌리기(board):
  B = [[0]*width for _ in range(height)]
  for x in range(width):
    for y in range(height):
      B[x][y] = board[y][x]
  return B

def 경사로를놓을수있는가(board, y, fromX, toX, LR):
  if LR == RIGHT:
    # l이 1인경우는 따로 처리를 해준다
    if l == 1:
      if record[y][fromX] == 경사로: return False
      else:
        record[y][fromX] = 경사로
        return True
    
    for x in range(fromX, toX):
      if 경사로 in [record[y][x], record[y][x+1]]: return False
      diff = board[y][x] - board[y][x+1]
      if diff != 0: return False
    for x in range(fromX, toX+1): record[y][x] = 경사로
    return True
  
  elif LR == LEFT:
    # l이 1인경우는 따로 처리를 해준다
    if l == 1:
      if record[y][fromX] == 경사로: return False
      else:
        record[y][fromX] = 경사로
        return True
      
    for x in range(fromX, toX, -1):
      if 경사로 in [record[y][x-1], record[y][x]]: return False
      diff = board[y][x] - board[y][x-1]
      if diff != 0: return False
    for x in range(fromX, toX, -1): record[y][x] = 경사로
    return True
  
def 가로확인(board):
  count = 0
  for y in range(height):
    OK = True
    for x in range(width-1):
      diff = board[y][x] - board[y][x+1]
      if abs(diff) > 1: OK = False
      elif diff == 1:
        if x+l >= width: OK = False
        else: OK = 경사로를놓을수있는가(board, y, x+1, x+l, RIGHT)
      elif diff == -1:
        if x-(l-1) < 0: OK = False
        else: OK = 경사로를놓을수있는가(board, y, x, x-(l-1), LEFT)
      if OK is False: break
    if OK is True: count += 1
  return count
  
def answer():
  global board, record
  boardTemp = deepcopy(board)
  recordTemp = deepcopy(record)
  count = 가로확인(board)
  record = recordTemp
  board = 보드돌리기(boardTemp)
  count += 가로확인(board)
  return count

print(answer())

Add Comment