백준 구현 대비 아기상어

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

초기접근

도식화
1. 먹을 수 있는 물고기 갯수 파악
2. 먹을 수 있는 물고기들의 좌표 파악 (리스트로 반환)
3. 리스트에서 하나씩 좌표를 꺼내가며 bfs 연산, 이때 도달할 수 없는 곳이면 false 반환, 도달할 수 있는 곳이면 destlist라는 배열 변수에 append
4. destlist의 길이가 0이라면 반복문 break, 1 이라면 해당 원소의 위치로 이동, 1이상이라면 정렬 기준으로 sort()해준 후 0번째 원소 위치로 이동
5. 1번부터4번 반복
결과. 시간초과

초기코드

from collections import deque

def fishplace(graph,sharksize):
  answer=[]
  for i in range(len(graph)):
    for j in range(len(graph[0])):
      if 0<graph[i][j]<sharksize:
        answer.append([i,j])
  
  return answer

def distance(si,sj,fi,fj,movelist,graph,sharksize,destlist):
  visited=[[0 for i in range(len(graph[0]))] for j in range(len(graph))]
  visited[si][sj]=1
  queue=deque()
  queue.append([si,sj,0])
  while queue:
    cur=queue.popleft()
    curi,curj,curd=cur[0],cur[1],cur[2]
    if curi==fi and curj==fj:
      destlist.append(cur)
    for mo in movelist:
      ni=curi+mo[0]
      nj=curj+mo[1]
      if 0<=ni<len(graph) and 0<=nj<len(graph[0]) and graph[ni][nj]<=sharksize and visited[ni][nj]==0:
        queue.append([ni,nj,curd+1])
        visited[ni][nj]=1
  

N=int(input())
time=0
sharksize=2
eatfish=0

movelist=[[1,0],[0,1],[-1,0],[0,-1]]
graph=[]
si,sj=None,None
for i in range(N):
  graph.append(list(map(int, input().split())))

for i in range(N):
  for j in range(N):
    if graph[i][j]==9:
      si,sj=i,j
      graph[si][sj]=0


while True:
  places=fishplace(graph,sharksize)
  if len(places)==0:
    break
  destlist=[]
  for pl in places:
    distance(si,sj,pl[0],pl[1],movelist,graph,sharksize,destlist)
  
  if len(destlist)==0:
    break
  elif len(destlist)==1:
    time+=destlist[0][2]
    eatfish+=1
    graph[destlist[0][0]][destlist[0][1]]=0
    si,sj=destlist[0][0],destlist[0][1]
  else:
    destlist.sort(key=lambda x:(x[2],x[0],x[1]))
    time+=destlist[0][2]
    eatfish+=1
    graph[destlist[0][0]][destlist[0][1]]=0
    si,sj=destlist[0][0],destlist[0][1]

  if eatfish==sharksize:
    sharksize+=1
    eatfish=0


print(time)

문제 발생 이유

시간 초과가 발생한 이유는 연산의 불필요한 중복이 너무 많이 발생한 것에 있었음. 초기 접근의 도식화 과정의 1,2,3번은 사실 나누어줄 필요가 없는 프로세스였다. 왜냐하면 bfs를 순회하는 과정에서 자연스럽게 도달할 수 있는 곳과 없는곳이 나누어지게 되고, 이렇게 나누어진 결과들을 결과물 배열안에 집어넣고 결과물 배열만 return 하면 되는 과정이었음. 이렇게 반환된 결과물 배열을 문제에서 요구한 기준에 맞게 sort하면 끝.

해결 코드

from collections import deque
sharksize=2
N=int(input())
graph=[]
curi,curj=0,0
eat=0
time=0
for i in range(N):
  graph.append(list(map(int, input().split())))

for i in range(N):
  for j in range(N):
    if graph[i][j]==9:
      curi,curj=i,j
      graph[i][j]=0
    
def bfs(ci,cj,cd,N,sharksize):
  movelist=[[-1,0],[0,-1],[1,0],[0,1]]  # 안일한 생각
  queue=deque()
  queue.append([ci,cj,cd])
  curlist=[]
  visited=[[0 for j in range(N)] for i in range(N)]
  visited[ci][cj]=1
  while queue:
    cur=queue.popleft()
    ci,cj,cd=cur[0],cur[1],cur[2]
    if 0<graph[ci][cj]<sharksize:
      curlist.append(cur)
    for mo in movelist:
      ni,nj,nd=ci+mo[0],cj+mo[1],cd+1
      if 0<=ni<N and 0<=nj<N and 0<=graph[ni][nj]<=sharksize and visited[ni][nj]==0:
        queue.append([ni,nj,nd])
        visited[ni][nj]=1
  curlist.sort(key=lambda x:(x[2],x[0],x[1]))
  if len(curlist)==0:
    return False
  return curlist[0]

while True:
  cur=bfs(curi,curj,0,N,sharksize)
  if cur:
    eat+=1
    curi,curj,curd=cur[0],cur[1],cur[2]
    graph[curi][curj]=0
    time+=curd
    if eat==sharksize:
      eat=0
      sharksize+=1

  else:
    break

print(time)

알고리즘 문제를 풀 때 도식화를 하는 과정까진 좋다. 그러나 1차 도식화를 작성한 후 중복될 수 있는 과정들은 최대한 하나로 합쳐주는 습관을 들여야 할듯