[BOJ] 16236번 - 아기 상어 (삼성 SW 기출 + deque 고찰2)

이번주 삼성 SW역량 테스트를 준비하면서 풀어 봤던 문제들을 풀어보는 중이었다.

그래서 문제들 중 상어 관련 문제인 아기 상어를 다시 풀어봤다. bfs() 알고리즘은 첫번째 원소 pop()과정을 매번 하므로

당연히 deque를 쓰는 것이 시간을 줄인다고 생각했다.

그런식으로 쭉 문제들을 풀어보다가 이번 문제에서 의문점을 하나 품게 되었고, 오늘 몇 가지 실험을 한 뒤 알게 되었다.

 

우선 문제에 대한 풀이를 해보자. 저번에 풀었던 코드와 이번에 풀었던 코드와의 차이점은 오직 자료구조 하나이다.

bfs() 에서 list() 를 쓰느냐 deque()을 쓰느냐 인데... 왜 deque()이 느릴까? 답은 풀이 이후 설명하겠다.

 

 

www.acmicpc.net/problem/16236

16236번: 아기 상어

풀이과정

사실 이렇게 구현이 힘든 문제들은 문제를 수시로 확인하면서 푸는 편이다. 자꾸 조건들을 까먹기도하고 최대한 한 번 짰던 코드를

수정할 일 없도록 하기 위함이다.

 

- 아기상어는 자기 자신보다 작은 물고기만 먹을 수 있다.

- 아기상어는 자기 자신보다 큰 물고기는 지나 갈 수 없다. (즉 크기가 같은 물고기는 먹을 수 없지만 지나 갈 순 있다.)

- 먹이는 아기상어와 가장 가까운 물고기를 먹는다.

- 먹을 수 있는 먹이가 여러마리라면 제일 위, 제일 왼쪽의 것을 먹는다.

 

시작 전) 공간에 물고기들을 볼 때 아기상어는 9로 되어 있다. 만약 아기상어가 위치를 옮길 때 해당 자리를 0으로 바꾸어 줘야 한다.

안 바꿔주면 아기상어는 자기자신의 크기가 2인데 비해 9를 못 지나가기때문에 예외 케이스가 생긴다.

 

1. 아기 상어를 찾은 뒤, bfs를 돌린 뒤 가장 가까운 물고기들을 담는다.

글쓴이는 bfs를 돌면서 가장 작은 것을 담았다. 물론 최솟값이 바뀌면 리스트도 계속 바뀌는 과정을 통해 잘 바꾸었다. (2번째 코드)

 

2. 가장 가까운 물고기들 중 제일 왼쪽 위의 것을 반환한다.

간단히 sort()를 통해 우선순위를 (행, 열)을 기준으로 해주면 된다.

 

3. 아기상어는 물고기를 먹고 그 자리에 위치한다.

원래 있었던 아기상어의 위치를 0으로 바꿔주고 먹은 물고기자리를 9로 바꾸어줘도 된다.

(계속 0을 하기 싫다면 맨 처음 부터 아기상어가 있는 위치를 0으로 둬도 된다. -> 코드 보면서 이해)

 

4. 아기상어가 엄마를 호출 하기 전까지 반복한다.

 

 

아래는 2개의 코드가 있다. 첫번째는 list, 두번째는 deque이다.

 

첫번째

#첫번째 코드 (list사용)

from sys import stdin

std = stdin.readline
N = int(std())
shark = []

for i in range(N):
    shark.append(list(map(int, std().split())))

huge, baby, eat = 2, [0, 0], 0  # 아기상어 크기, 위치, 현재먹은 개수
for i in range(N):
    for j in range(N):
        if shark[i][j] == 9:
            baby = [i, j]

q = []
nr, nc = [-1, 0, 1, 0], [0, -1, 0, 1]

check = [[0 for i in range(N)] for j in range(N)]


def find_food():
    check = [[0 for i in range(N)] for j in range(N)]
    f_r, f_c, dd = q[-1]
    check[f_r][f_c] = 1
    F = []
    dist = -1
    while q:
        r, c, d = q.pop(0)
        if d == dist:
            break
        for i in range(4):
            dr = r + nr[i]
            dc = c + nc[i]
            if 0 <= dr < N and 0 <= dc < N:
                if check[dr][dc] == 0 and shark[dr][dc] <= huge:
                    check[dr][dc] = 1
                    if 0 < shark[dr][dc] < huge:
                        F.append((dr, dc, d+1))
                        dist = d+1
                    q.append((dr, dc, d+1))
    F = sorted(F, key=lambda x: (x[2], x[0], x[1]))
    if len(F) == 0:
        return -1
    else:
        return F[0]


answer = 0
aa = 0
food = []
while True:
    r, c = baby
    q.append((r, c, 0))
    food = find_food()
    if food == -1:
        break
    q = []
    shark[r][c] = 0
    new_r, new_c, dist = food
    baby = [new_r, new_c]
    shark[new_r][new_c] = 9
    eat += 1
    answer += dist

    if huge == eat:
        huge += 1
        eat = 0

print(answer)

 

 

두번째

# 두번째 코드 deque 사용


std = stdin.readline
N = int(std())
shark = []

for i in range(N):
    shark.append(list(map(int, std().split())))

huge, baby, eat = 2, [0, 0], 0  # 아기상어 크기, 위치, 현재먹은 개수
for i in range(N):
    for j in range(N):
        if shark[i][j] == 9:
            baby = [i, j]

q = []
nr, nc = [-1, 0, 1, 0], [0, -1, 0, 1]

check = [[0 for i in range(N)] for j in range(N)]


def find_food():
    check = [[0 for i in range(N)] for j in range(N)]
    f_r, f_c, dd = q[-1]
    check[f_r][f_c] = 1
    F = []
    dist = -1
    while q:
        r, c, d = q.pop(0)
        if d == dist:
            break
        for i in range(4):
            dr = r + nr[i]
            dc = c + nc[i]
            if 0 <= dr < N and 0 <= dc < N:
                if check[dr][dc] == 0 and shark[dr][dc] <= huge:
                    check[dr][dc] = 1
                    if 0 < shark[dr][dc] < huge:
                        F.append((dr, dc, d+1))
                        dist = d+1
                    q.append((dr, dc, d+1))
    F = sorted(F, key=lambda x: (x[2], x[0], x[1]))
    if len(F) == 0:
        return -1
    else:
        return F[0]


answer = 0
aa = 0
food = []
while True:
    r, c = baby
    q.append((r, c, 0))
    food = find_food()
    if food == -1:
        break
    q = []
    shark[r][c] = 0
    new_r, new_c, dist = food
    baby = [new_r, new_c]
    shark[new_r][new_c] = 9
    eat += 1
    answer += dist

    if huge == eat:
        huge += 1
        eat = 0

print(answer)

 

위의 코드는 각각 110 ~ 130ms, 220~40ms 정도 나왔다.

즉 , list로 작성한 코드가 더 작다는 말이다. 분명히 deque()에서 popleft()과정은 더 짧다고 생각했는데 왜 더 나온 것일까??

 

여러가지 추측을 하다가 실험을 해보았다.

 

다른 코드는 상관없고 deque()의 popleft()보다 list()의 pop(0) 보다 훨씬 빠르다는 것은 이미 고찰 1에서 실험을 해보았다.

그렇다면 다른 것은 list와 deque에 각각 append하는 과정이다.

 

10000개의 원소를 넣어볼 때 각각 시간을 재보았다.

from sys import stdin, getsizeof
from collections import deque
from math import floor
import time

N = 10000


start = time.time()
queue = [0 for i in range(N)]
end = time.time()
print("list: ", floor((end-start)*10000), "ms")


start = time.time()
deque = deque()
for i in range(N):
    deque.append(i)
end = time.time()
print("deque: ", floor((end-start)*10000), "ms")

결과는 아래와 같다.

 

결과 값

deque가 약 4~5배 정도 느린듯 하다.

 

같은 O(1)이지만 다른 결과를 보이는 것으로 보아 아마 상수값에서 차이나는 듯하다.

 

이것으로 궁금증을 해결했다.

 

 

www.acmicpc.net/board/view/67459#post

글 읽기 - 파이썬 고수님들 도와주세요 ㅠㅠ (답 포함)

질문하고 자문 자답 했음..