백준 16236번 문제(아기 상어) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

16236번: 아기 상어

 

정답 코드는 아래와 같습니다.

import copy
 
def findTopLeft(queue, n):
  tmp = []
  for x, y in queue:
    tmp.append(x*n + y)
  tmp.sort()
  X = tmp[0] // n
  Y = tmp[0] % n
  return X, Y
 
def isAvailable(x, y, arr, size, n, history):
  if 0 <= x < n and 0 <= y < n:
    if history[x][y] != 1:
      if arr[x][y] <= size:
        return True
  return False
 
def calc(n, start, arr, size):
  queue = [start]
  a, b = start
  history = [[0] * n for _ in range(n)]
  history[a][b] = 1
  for length in range(1, n*n):
    nextQueue = []
    eatableQueue = []
    for x, y in queue:
      for p, q in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if isAvailable(x+p, y+q, arr, size, n, history):
          nextQueue.append((x+p, y+q))
          history[x+p][y+q] = 1
          if 0 < arr[x+p][y+q] < size:
            eatableQueue.append((x+p, y+q))
    if len(eatableQueue) != 0:
      x, y = findTopLeft(eatableQueue, n)
      arr[a][b] = 0
      arr[x][y] = 9
      return length, x, y
    if len(nextQueue) == 0:
      return 0, 0, 0
    queue = copy.deepcopy(nextQueue)
 
def solve():
  n = int(input())
  arr = []
  for i in range(n):
    line = [int(x) for x in input().split()]
    for j in range(n):
      if line[j] == 9:
        start = (i, j)
        break
    arr.append(line)
  rst = 0
  size = 2
  cnt = 0
  while True:
    ret, a, b = calc(n, start, arr, size)
    if ret == 0:
      print(rst)
      return
    cnt += 1
    if cnt == size:
      size += 1
      cnt = 0
    rst += ret
    start = (a, b)
 
solve()
 

 

728x90

 

특별한 기법 없이 naiive 하게 아이디어를 떠올리고 그대로 풀면 되는 문제입니다. 일명 빡구현(?) 문제라고 할 수 있죠.

회사마다 다르겠지만, 실제 현직에서는 본 문제와 유사하게 단순한 요구사항에 대한 코드를 작성하는 경우도 많기 때문에 회사 입장에서는 실무 능력을 확인하기 좋은 문제라고 할 수 있습니다.

실제로 이 문제는 유명 대기업의 코딩테스트 기출문제이기도 합니다.

 

코드의 양이 상대적으로 많기 때문에 전체적으로 코드를 구조화 하는 능력과 추상화 하는 능력이 필요합니다.

이런 유형의 문제는 재미가 없고 코드는 길기 때문에 귀찮다고 연습하지 않는 사람들이 종종 있는데요.

연습을 미리 해놓지 않으면, 막상 실전에서 당황하여 잘 풀리지 않을 수 있으니, 빼먹지 말고 연습하시기를 권장합니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=n2jzdUT-Ctc 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)