Algorithm
백준
Python
경사로

경사로

문제 : https://www.acmicpc.net/problem/14890 (opens in a new tab)

내 풀이

풀이도 더럽고 풀었는데 기쁘지 않다... 푸는데 2시간 정도 걸린것 같다.
조건이 어떤식으로 걸리는지 몰라서 자꾸 조건을 걸고 풀고를 반복했는데 이게 단순한 구현능력의 문제인지 모르겠다.

N, L = map(int, input().split())
graph = []
 
for _ in range(N):
  line = list(map(int, input().split()))
  graph.append(line)
 
'''
바로 뒤 칸부터 들어와야함
'''
def check_column(v, d, visited) :
    lc = 0
    r, c = v
    nc = c
    if visited[nc] :
      return False, visited
    while -1 < nc < N :
      visited[nc] = True
      lc += 1
      if lc == L :
        return True, visited
      nc += d
      # 경사가 달라졌거나 이미 경사가 깔렸었으면
      if -1 < nc < N :
        if graph[r][nc] != graph[r][c] or visited[nc] :
         return False, visited
      else :
        break
 
    return False, visited
 
def check_row(v, d, visited) :
    lc = 0
    r, c = v
    nr = r
    if visited[nr] :
      return False, visited
    while -1 < nr < N :
      visited[nr] = True
      lc += 1
      if lc == L :
        return True, visited
      nr += d
      # 경사가 달라졌거나 이미 경사가 깔렸었으면
      if -1 < nr < N :
        if graph[nr][c] != graph[r][c] or visited[nr] :
          return False, visited
      else :
        break
 
    return False, visited
 
def main(graph):
  cnt = 0
 
  for r in range(N):
    prev = 0
    visited = [False for _ in range(N)]
    for c in range(N):
      if graph[r][c] == graph[r][prev] :
        pass
      elif graph[r][c] - 1 == graph[r][prev] : # 한 칸 올라간 경우
        result, visited = check_column([r,c - 1], -1, visited)
        if result :
          prev = c
        else :
          break
      elif graph[r][c] + 1 == graph[r][prev] : # 한 칸 내려간 경우
        result, visited = check_column([r,c], 1, visited)
        if result :
          prev = c
        else :
          break
      else :
        break
      # break 안당하고 마지막까지 왓으면 cnt 1 증가
      if c == N - 1 :
        cnt += 1
 
  for c in range(N):
    prev = 0
    visited = [False for _ in range(N)]
    for r in range(N):
      if graph[r][c] == graph[prev][c] :
        pass
      elif graph[r][c] - 1 == graph[prev][c] : # 한 칸 올라간 경우
        result, visited = check_row([r - 1,c], -1, visited)
        if result :
          prev = r
        else :
          break
      elif graph[r][c] + 1 == graph[prev][c] : # 한 칸 내려간 경우
        result, visited = check_row([r,c], 1, visited)
        if result :
          prev = r
        else :
          break
      else :
        break
      # break 안당하고 마지막까지 왓으면 cnt 1 증가
      if r == N - 1 :
        cnt += 1
  return cnt
 
print(main(graph))

다른 사람 풀이

import sys
 
N, L = map(int, sys.stdin.readline().split())
 
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
 
def check(line, L):
    # 경사로 생기는 곳 체크
    visited = [False for _ in range(N)]
    # 자리 차례로 탐색
    for i in range(0, N-1):
        # 바로 다음 위치의 높이가 같으면 continue
        if line[i] == line[i+1]:
            continue
        # 다음 위치의 높이 차이가 1 넘게 나면 False
        elif abs(line[i]-line[i+1]) > 1:
            return False
        # 현재 높이가 다음 높이 보다 높으면 오른쪽 높이가 같은지 체크
        elif line[i] > line[i+1]:
            temp = line[i+1] # 다음 높이
            for j in range(i+1, i+L+1):
                # 경사 길이가 범위 안이면
                if 0 <= j < N:
                    # 경사 놓을 위치의 높이가 하나라도 다르면
                    if temp != line[j]:
                        return False
                    # 높이는 다 같은데 이미 경사가 놓여진 곳이면
                    elif visited[j]:
                        return False
                    # 경사 놓기
                    visited[j] = True
                # 경사 길이가 범위 벗어나면
                else:
                    return False
        # 다음 높이가 현재 높이 보다 높으면 왼쪽 높이가 같은지 체크
        else:
            temp = line[i]
            for j in range(i, i-L, -1):
                # 경사 길이가 범위 안이면
                if 0 <= j < N:
                    # 경사 놓을 위치의 높이가 하나라도 다르면
                    if temp != line[j]:
                        return False
                    # 높이는 다 같은데 이미 경사가 놓여진 곳이면
                    elif visited[j]:
                        return False
                    # 경사 놓기
                    visited[j] = True
                # 경사 길이가 범위 벗어나면
                else:
                    return False
    return True
 
answer = 0
# 가로 길 체크
for i in board:
    if check(i, L):
        answer += 1
 
# 세로 길을 체크하기 위해 변환해서 넣어줌
for i in range(N):
    temp = []
    for j in range(N):
        temp.append(board[j][i])
    if check(temp, L):
        answer += 1
 
print(answer)