[골드 III] 16236번. 아기 상어

 문제 

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

16236번: 아기 상어

 사용 언어 

Python3

 풀이 과정 

조건이 진짜 많아서 풀기 까다로웠던 문제...

조건을 정리해보니 다음과 같았다.

# 처음 아기상어 크기는 2
# 1초에 상하좌우로 한 칸씩 이동
# 자기보다 큰 물고기가 있는 칸은 지나갈 수 없음
# 자기보다 작은 크기의 물고기만 먹을 수 있음
# 자기랑 같은 크기면 지나갈수만 있음
# 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가
# 먹을 수 있는 물고기가 1마리 이상이면 가까운 물고기를 먹으러 감
    # 최소 거리 물고기가 여러 마리면 가장 위에 있는 물고기
        # 또 여러 마리면 가장 왼쪽에 있는 물고기를 먹음
# 더이상 먹을 수 있는 물고기가 공간에 없을 때 끝

BFS로 풀어야하는건 알겠는데 일단 상어 위치인 9를 찾아야 하고 거기서 또 물고기를 먹을 때마다 크기가 증가하고 이런 걸 고려하려고 하니 어지러웠다😵

 

그래서 구글링으로 블로그의 도움을 좀 받았고 내 스타일대로 고치며 이해했다.

사실 BFS + 벡터 상하좌우를 쓰는 틀은 거의 비슷한 것 같고 거기에 조건을 하나씩 추가하면 되는데 연습이 많이 필요한듯 하다...

 

어쨌든 맞았습니다!!

 제출 답안 

from sys import stdin
input = stdin.readline

def eatFish(x, y, sharkSize):
    distance = [[0] * N for _ in range(N)]
    visited = [[0] * N for _ in range(N)]
    queue = [(x, y)]
    visited[x][y] = 1
    tmp = []
    for curX, curY in queue:
        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
                if space[nx][ny] <= sharkSize:
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
                    distance[nx][ny] = distance[curX][curY] + 1
                    if space[nx][ny] < sharkSize and space[nx][ny] != 0:
                        tmp.append((nx, ny, distance[nx][ny]))
    return sorted(tmp, key = lambda x: (-x[2], -x[0], -x[1]))
        

if __name__ == "__main__":
    N = int(input())
    space = [list(map(int, input().split())) for _ in range(N)]

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

    fish = 0
    x, y, size = 0, 0, 2
    for i in range(N):
        for j in range(N):
            if space[i][j] == 9:
                x = i
                y = j

    count = 0
    result = 0
    while True:
        fishInfo = eatFish(x, y, size)
        if len(fishInfo) == 0:
            break
        nx, ny, dist = fishInfo.pop()
        
        result += dist
        space[x][y], space[nx][ny] = 0, 0

        x, y = nx, ny
        count += 1
        if count == size:
            size += 1
            count = 0

    print(result)

 다른 사람 코드 

from sys import stdin
input = stdin.readline
def update(y,x):
    global shark
    sy, sx, v, l = shark
    fish_map[y][x]=0
    shark = [y,x,v+1,v+1] if l==1 else [y,x,v,l-1]

def bfs():
    global shark
    sy,sx,v,_ = shark
    visited = [[0]*N for _ in range(N)]
    visited[sy][sx]=1
    queue = [(sy,sx)]
    depth = 0
    while queue:
        depth+=1
        can_eat_fishes = []
        len_q = len(queue)
        for _ in range(len_q):
            y,x= queue.pop(0)
            for nxt_y,nxt_x in ((y-1,x),(y,x-1),(y,x+1),(y+1,x)):
                if (0<=nxt_y<N and 0<=nxt_x<N) and not visited[nxt_y][nxt_x] and fish_map[nxt_y][nxt_x]<=v:
                    visited[nxt_y][nxt_x]=1
                    if 0< fish_map[nxt_y][nxt_x] < v:
                        can_eat_fishes.append((nxt_y,nxt_x))
                    else:
                        queue.append((nxt_y, nxt_x))
        if can_eat_fishes:
            fish = sorted(can_eat_fishes)[0]
            update(*fish)    # shark, fish_map
            return depth
    return 0

N = int(input())
fish_map = [];shark = [];start_flag = False
for y in range(N):
    row = list(map(int,input().split()))
    for x,v in enumerate(row):
        if v == 9:
            shark = [y,x,2,2] #y,x,size,life
        elif not start_flag and v!=0:
                start_flag = (v<2)
    fish_map.append(row)
fish_map[shark[0]][shark[1]] = 0
time =0
if start_flag:
    while True:
        tmp_time = bfs()
        if not tmp_time: break
        time+=tmp_time
print(time)

➡ 와 나는 300ms 나왔는데 2년 전거라고 하지만 56ms라니!

 

보고 느낀점을 적어봤다.

1. 나는 이중 for문을 돌면서 9를 찾는 방식이 마음에 안들어서 입력받을 때 검증하는 방법을 생각했는데, 대부분의 코드가 그냥 이중 for문에서 찾는 것 같다.
2. 그리고 python에서는 ;(세미콜론)이 절대 안쓰이는 줄 알았는데 한 줄로 이어서 쓰려면 구분자로 사용되나 보다! 초기화를 여러개 해야할 때 여러줄을 쓰는 게 싫어서 저렇게 하신 것 같다.
2. 사실 이렇게까지 큰 시간차가 나는 이유를 모르겠다... 더 공부해야지