[Python] 백준 14890 경사로

1. 문제 - 백준 14890 경사로

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

 

💡알고리즘 - 구현

• 삼성SW역량테스트 문제이다. 문제의 조건에 맞게 구현 잘하면 되는 문제..!

✅ 풀이

n, l = map(int, input().split())   # l: 경사로의 길이, 갯수 무제한
board = []
for i in range(n):
  board.append(list(map(int, input().split())))
answer = 0
    
# 경사로를 놓음으로서 길을 만들 수 있는지 판단하는 함수
# 경사로를 놓은 곳에 또 경사로를 놓는 경우 -> False
# 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우 -> False
# 낮은 지점의 칸의 높이가 모두 같지 않거나, L개 연속 X -> False
def can_road(road):
  visited = [False] * n   # 경사로 설치 여부를 판단하는 배열
  if len(set(road)) == 1:  # 모두 같은 숫자로 이루어져있는 경우, 길이므로 바로 return True
    return True

  for i in range(1, n):
    diff = road[i-1] - road[i]
    if abs(diff) > 1:   # 낮은 칸과 높은 칸의 차이가 1보다 크다면, 경사로를 놓을 수 없음 -> 길이 될 수 없음
      return False

    if diff == -1:    # 좌측으로 경사로 놓기
      for j in range(l):
        if i-1-j < 0:   # 범위를 벗어나 경사로를 놓을 수 없는 경우 
          return False
        if visited[i-1-j]: # 이미 경사로를 놓은 경우
          return False
        if road[i-1] != road[i-1-j]:
          return False
        visited[i-1-j] = True
    elif diff == 1:     # 우측으로 경사로 놓기
      for j in range(l):
        if i + j >= n:   # 범위를 벗어나 경사로를 놓을 수 없는 경우 
          return False
        if visited[i+j]: # 이미 경사로를 놓은 경우
          return False
        if road[i] != road[i+j]:
          return False
        visited[i+j] = True

  return True
for i in range(n):
  row = board[i]               # i번째 가로줄
  col = [board[r][i] for r in range(n)]  # i번째 세로줄
  # 가로
  if can_road(row):   # 길이 될 수 있으면
    answer += 1
  # 세로
  if can_road(col):   # 길이 될 수 있으면
    answer += 1

print(answer)

 

1) 매 가로, 세로 줄 마다 길이 될 수 있는지를 판단해서 answer에 더하면 된다.

2) 길이 될 수 있는지를 매번 판단하니까, 이를 따로 함수화하면 편하기도 하고 가독성이 좋아진다.
조건을 잘 읽고 조건에 맞게 return True / False를 해주는 can_road 함수를 하나 만든다.

def can_road(road):
  visited = [False] * n   # 경사로 설치 여부를 판단하는 배열
  if len(set(road)) == 1:  # 모두 같은 숫자로 이루어져있는 경우, 길이므로 바로 return True
    return True

  for i in range(1, n):
    diff = road[i-1] - road[i]
    if abs(diff) > 1:   # 낮은 칸과 높은 칸의 차이가 1보다 크다면, 경사로를 놓을 수 없음 -> 길이 될 수 없음
      return False

    if diff == -1:    # 좌측으로 경사로 놓기
      for j in range(l):
        if i-1-j < 0:   # 범위를 벗어나 경사로를 놓을 수 없는 경우 
          return False
        if visited[i-1-j]: # 이미 경사로를 놓은 경우
          return False
        if road[i-1] != road[i-1-j]:
          return False
        visited[i-1-j] = True
    elif diff == 1:     # 우측으로 경사로 놓기
      for j in range(l):
        if i + j >= n:   # 범위를 벗어나 경사로를 놓을 수 없는 경우 
          return False
        if visited[i+j]: # 이미 경사로를 놓은 경우
          return False
        if road[i] != road[i+j]:
          return False
        visited[i+j] = True

  return True

 

3) 경사로 설치 여부를 알아야하므로, 경사로가 설치의 여부를 판단하기 위한 visited 배열을 만들고, 이후 경사로를 설치한 칸에 True 처리함으로써 판단한다.

• 그 길이의 모든 칸의 높이가 같다 -> len(set(road)) == 1이라면 중복을 제거해주는 집합의 크기가 1이라는 것은 길의 모든 칸 길이가 같다는 의미이므로 바로 return True해준다.
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우, 경사로를 놓을 수 없음 -> abs(diff) > 1: return False
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않는 경우
  경사로를 놓다가 범위를 벗어나는 경우
  -> l 만큼의 for문을 통해 좌측으로 경사로 놓는 경우와 우측으로 경사로 놓는 경우 모두 판단하기

    if diff == -1:    # 좌측으로 경사로 놓기
      for j in range(l):
        if i-1-j < 0:   # 범위를 벗어나 경사로를 놓을 수 없는 경우 
          return False
        if visited[i-1-j]: # 이미 경사로를 놓은 경우
          return False
        if road[i-1] != road[i-1-j]:  # 경사로를 놓을 곳의 높이가 서로 같지 않음
          return False
        visited[i-1-j] = True   # 경사로 놓기
    elif diff == 1:     # 우측으로 경사로 놓기
      for j in range(l):
        if i + j >= n:   # 범위를 벗어나 경사로를 놓을 수 없는 경우 
          return False
        if visited[i+j]: # 이미 경사로를 놓은 경우
          return False
        if road[i] != road[i+j]:     # 경사로를 놓을 곳의 높이가 서로 같지 않음
          return False
        visited[i+j] = True     # 경사로 놓기

 

여기서 되지 않는 조건에 해당하면 바로 return False 하는 이유는, 어차피 경사로를 하나라도 놓지 못하는 환경이면 그 길은 길이 될 수 없으므로 바로 return False로 하면 된다.

 

💡 놓친 부분

"경사로를 놓는 곳에 또 경사로를 놓는 경우" 경사로를 놓을 수 없는 조건에서 가로, 세로로 경사로가 겹치면 안되는거 아닌가?때문에

많이 헤맸는데.. 질문 게시판 보면 이부분은 고려 안하고 가로, 세로만 경사로를 놓아서 길로 만들 수 있는지 판단하면 되는 문제였다.

나처럼 헷갈려한 사람이 많은듯..