백준(BOJ) 16236 아기 상어(Python)

문제 내용.

 

BFS 문제.

아기 상어가 있는 위치로부터 같은 거리에 있는 물고기들 중 먹을 수 있는 물고기의 x,y좌표를 모두 저장한 뒤, 물고기의 좌표를 x,y좌표 순으로 오름차순 정렬해서 첫 번째 위치로 상어가 이동해 물고기를 먹는다. 만약 해당 거리에 물고기가 없다면 거리를 1 증가시켜 다시 물고기를 탐색한다.

나머지는 문제에서 주어진 대로 처리했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
"""

import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
dx=[-1,0,0,1]
dy=[0,-1,1,0]
n=int(input())
L=[]
queue=deque()
ans=0
a=0
b=0
visited=[[0]*n for i in range(n)]
for i in range(n):
    L.append(list(map(int,input().split())))
    for j in range(n):
        if L[i][j]==9:
            queue.append([i,j,0])
            L[i][j]=0
            visited[i][j]=1
        elif L[i][j]:
            a+=1
size=2
ate=0
dist=1
check=[]
while queue and b<a:
    x,y,k=queue.popleft()
    if k>=dist:
        if len(check):
            ans+=k
            check.sort()
            x,y=check[0]
            L[x][y]=0
            check=[]
            dist=1
            k=0
            b+=1
            ate+=1
            if size==ate:
                size+=1
                ate=0
            queue=deque()
            visited=[[0]*n for i in range(n)]
            visited[x][y]=1
        else:
            dist+=1
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<n and 0<=ny<n and not visited[nx][ny]:
            if L[nx][ny]==0 or L[nx][ny]==size:
                queue.append([nx,ny,k+1])
            elif L[nx][ny]<size:
                check.append([nx,ny])
                queue.append([nx,ny,k+1])
            visited[nx][ny]=1
print(ans)

 

물고기를 먹을 때마다 visited를 초기화해주는 것이 핵심.

구현이 좀 귀찮았다.

신촌캠프 문제.