[BOJ] 14890번 경사로 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

문제에서 N이 100까지의 범위여서 $O(N^4)$까지 가능하겠다고 접근했고, 비효율적이어도 $O(N^4)$이 가능하니 구현했다.

시간복잡도를 더 최적화하는 방법이 존재했을 것 같다. 경사로를 설치할 수 있는지 validation을 할때의 $O(N)$을 매번 for문으로 체크하는게 아닌 그 이전의 for문에서 돌면서 같이 체크하도록 하는 방법으로. 시간되면 한번 고민해봐야겠다.

정답 제출할때 테스트케이스 맞았다고 제출하는게 아닌 내가 짠 코드 전체를 곱씹으면서 시간 들여서 정확히 쭉 보고 제출하는게 좋겠다고 느꼈다. 어이없는 실수를 방지할 수 있고, 예외를 발견할 확률이 올라간다.

추가로 문제를 처음에 읽고 이해하는데 시간을 확실히 많이 의식해서 투자하자.

def is_valid(i, installed, road, height):
  # !높이도 체크해야 함!
  # 범위안에 있고 경사로 설치 안되어 있을 때
  if 0<=i<N and road[i]==height and not installed[i]:
    return True
  return False
  

def check_one_road(road):
  installed = [False]*N # 경사로 설치 여부
  
  for ptr in range(N-1): # 하나씩 체크(왼쪽칸 기준으로 탐색)
    if road[ptr] == road[ptr+1]+1: #왼쪽이 한칸 더 큰 경우
      check_height = road[ptr+1]
      # 경사로 설치 가능한지 체크 => 불가능하면 False 바로 리턴
      for i in range(L):
        if not is_valid(ptr+1+i, installed, road, check_height): #ptr+1부터
          return False
          
      # 경사로 설치(installed=True로)
      for i in range(L):
        installed[ptr+1+i] = True
      
    elif road[ptr]+1 == road[ptr+1]: # 오른쪽이 한칸 더 큰 경우
      check_height = road[ptr]
      # 경사로 설치 가능한지 체크 => 불가능하면 False 바로 리턴
      for i in range(L):
        if not is_valid(ptr-i, installed, road, check_height):# ptr부터
          return False

      # 경사로 설치(installed=True로)
      for i in range(L):
        installed[ptr-i] = True
      
    elif road[ptr]==road[ptr+1]: # 높이 같은 경우
      continue # 다음 칸으로 이동
    else: # 2칸 이상 차이 나는 경우 바로 False 반환
      return False
      
  return True


N, L = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

ans = 0
# 가로 방향
for i in range(N):
  road = []
  for j in range(N):
    road.append(graph[i][j])
  if check_one_road(road):
    ans +=1

# 세로 방향
for i in range(N):
  road = []
  for j in range(N):
    road.append(graph[j][i])
  if check_one_road(road):
    ans +=1

print(ans)