16236_아기상어

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

16236번: 아기 상어

 

 

 

 

이역시 이해는 하기쉬운 구현문제였다. 하지만 시간을 엄청엄청 많이 잡아먹었다...

 

 

다른부분보다 문제되는 부분은 바로

 

 

• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

해당 부분이다. 이부분을 매우매우 매우 유심해 봐야한다.

 

처음에는 그저 상,좌,우,하 순서로 bfs를 탐색하면 될줄 알았다. 하지만 이렇게 하면 틀리게 된다. 예를들어서

 

 

5
0 0 0 0 0
0 0 0 0 0
0 0 9 0 1
0 1 0 0 0
0 2 2 0 0

 

다음과같은 예가 있을때 오른쪽 1을 먼저 먹어야 하지만 bfs를 상,좌,우,하로 할 경우 밑의 1을 먹게 된다 

 

즉,

 

0 0 5 0 0

0 6 1 7 0

8 2 0 3 10

0 9 4 11 0

0 0 12 0 0

 

위와같은 순서로 bfs탐색을하기에 발생되는 현상이다. 따라서 최소 거리들의 집합을 모은 후에 정렬해주는 과정이 필요하다.

 

 

 

또한 bfs탐색할때 내가 항상 실수하는 것을 발견했다. 바로 visit배열을 이용할때 que에 넣어주는 경우에 visit을 설정해줘야지 que가 엄청나게 커지는것을 막아줄 수 있다.

import sys
from collections import deque
input = sys.stdin.readline

dx = [ -1 , 0 , 0 , 1 ]
dy = [ 0 , -1 , 1 , 0 ]

n = int(input())
sea = [ list(map(int,input().split())) for _ in range(n)]
size = 2
cnt = 0
for i in range(n):
    for j in range(n):
        if sea[i][j] == 9:
            x,y = i,j

def bfs(x,y):
    global size,cnt
    q = deque([(x,y,0)])
    visit = [ [False]*n for _ in range(n)]
    temp = []
    distance = 1e9
    while q:
        x,y,dist = q.popleft()
        visit[x][y] = True

        for d in range(4):
            nx,ny = x + dx[d], y + dy[d]

            if 0<=nx<n and 0<=ny<n and not visit[nx][ny] and dist < distance:

                if sea[nx][ny] <= size:
                    q.append((nx,ny,dist+1))
                    visit[nx][ny] = True
                    if sea[nx][ny] < size and sea[nx][ny] !=0:
                        temp.append((nx,ny,dist+1))
                        distance = dist+1

    return sorted(temp,key=lambda x: (x[2],x[0],x[1]))

result = 0
while True:
    sea[x][y] = 0
    temp = bfs(x,y)
    if len(temp) ==0:
        break
    x,y,dist = temp[0]

    sea[x][y] = 9
    result += dist
    cnt += 1
    if size == cnt:
        size += 1
        cnt = 0

print(result)