[백준, 삼성 기출] 16236_아기 상어 (Python) - 다시 풀기

16236_아기 상어 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 16236번: 아기 상어

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 물고기 위치 및 상어를 이차원 배열로 담는다.
>> 상어의 위치에서 bfs 돌린다. -> 이때 해당 물고기를 찾으면서 시간이 최소인 경우에 그 물고기를 먹는다. 또한 먹은 물고기 좌표를 따로 queue에 담아둔다.
>> 시간이 걸린 물고기가 2개 이상인 경우 각 물고기 좌표를 비교해서 더 작은쪽을 먹고 해당 물고기 좌표를 따로 queue에 담아둔다.

>> 다시 상어의 시작 위치는 queue에 담긴 좌표가 될 것이다.
>> bfs를 다시 돌린다.

>> 어떤 단위 등으로 함수를 나눌 것인지 잘 판단하자 ★

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
0 0 0
0 0 0
0 9 0

- 예제 출력 1 -
0

- 예제 입력 2 -
3
0 0 1
0 0 0
0 9 0

- 예제 출력 2 -
3

- 예제 입력 3 -
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

- 예제 출력 3 -
14

- 예제 입력 4 -
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

- 예제 출력 4 -
60

- 예제 입력 5 -
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1

- 예제 출력 5 -
48

(3) 코드

# 시간초과

from collections import deque

n = int(input())
graph = list(list(map(int, input().split())) for _ in range(n))

# 상어 이동
def move(q, graph, time, f_graph, size):
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    visited = [[0]*n for _ in range(n)]

    while q:
        x, y = q.popleft()

        # x,y가 찾는 물고기 좌표라면
        if graph[x][y] < size and graph[x][y] > 0:
            f_graph.append((x, y, visited[x][y]))

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

            # 범위 안에 있고 size가 같거나 작으면
            if 0<=nx<n and 0<=ny<n:
                if graph[nx][ny] <= size and visited[nx][ny] == 0:
                    visited[nx][ny] += visited[x][y] + 1
                    q.append((nx,ny))

        if not q:
            return f_graph


q = deque()
time = 0
total_time = 0
size = 2
feed = 0

while 1:

    # 0. 상어 좌표를 찾는다.
    for x1 in range(n):
        for y1 in range(n):
            if graph[x1][y1] == 9:
                s_x = x1
                s_y = y1
                break

    q.append((s_x, s_y))

    # 1. 상어 이동
    f_graph = []
    f_graph = move(q, graph, time, f_graph, size)

    # 2. 찾는 물고기 좌표 비교
    if len(f_graph) >= 1:
        graph[s_x][s_y] = 0

        # 시간, x좌표, y좌표 순서의 오름차순으로 정렬 ★
        f_graph.sort(key=lambda x : (x[2], x[0], x[1]))

        # print(f"f_graph 입니다. {f_graph}")
        f_x, f_y, time = f_graph[0]
        f_graph = []

        graph[f_x][f_y] = 9

        feed += 1

        total_time += time
        time = 0
        if size == feed:
            size += 1
            feed = 0

    elif len(f_graph) == 0:
        print(total_time)
        break

from collections import deque

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

# n = int(6)
# arr = [[6, 0, 6, 0, 6, 1],
#  [0, 0, 0, 0, 0, 2],
#  [2, 3, 4, 5, 6, 6],
#  [0, 0, 0, 0, 0, 2],
#  [0, 2, 0, 0, 0, 0],
#  [3, 9, 3, 0, 0, 1]]

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

sx, sy = 0, 0

# 상어의 위치를 찾는다.
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:

            # 상어위치를 0으로 만들어준다.
            arr[i][j] = 0
            sx, sy = i, j
            break

size = 2
move_num = 0
feed = 0

while True:
    q = deque()
    q.append((sx, sy, 0))
    visited = [[False] * n for _ in range(n)]
    flag = 1e9
    fish = []

    while q:
        x, y, count = q.popleft()

        # count가 flag(먹이를 찾은 지점까지의 거리)보다 커지는 경우
        # 더 이상 찾을 필요가 없으므로 break 한다.
        if count > flag:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어나는 경우 못지나감
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue

            # size 보다 큰 경우 못지나감 방문한경우 못 지나감
            if arr[nx][ny] > size or visited[nx][ny]:
                continue

            # size보다 작은 물고기가 있는 경우
            if arr[nx][ny] != 0 and arr[nx][ny] < size:
                fish.append((nx, ny, count + 1))
                print(f"fish 를 먹었습니다 : {fish}")
                flag = count
                print(f"count 입니다 {count}")
            visited[nx][ny] = True

            # 내가 생각하는 핵심 부분★
            q.append((nx, ny, count + 1))

    # 먹이를 먹은 경우(같은 거리)
    if len(fish) > 0:
        fish.sort()
        print(f"먹은 fish입니다 : {fish}")
        x, y, move = fish[0][0], fish[0][1], fish[0][2]
        move_num += move
        feed += 1

        # 먹은 fish자리는 0으로 바꿔준다.
        arr[x][y] = 0

        if feed == size:
            size += 1
            feed = 0

        # 상어의 위치를 바꿔준다. ★
        sx, sy = x, y
    else:
        break

print(move_num)

(4) 정리

생각하는 로직은 맞았는데 생각한 로직대로 구현을 못했다..
문제 구현하고 답안보고 이해하는데까지 3시간걸렸다.

(5) 참고

참고 풀이