문제

해결 방법을 생각해 보자.

방법 1: 생각 나는 대로:

  • 기본 로직

    • 물고기 크기/위치를 기준으로 정렬한다.
    • 먹을 수 있는 물고기만 담는다.
    • 거리를 계산한다.
    • 가장 짧은 거리의 물고기만 먹는다.
    • 먹은 수대로 상어 크기를 올린다.

  • 핵심 로직

    • 상어의 성장 여부 확인
    • 먹을 수 있는 물고기만 담기
    • 거리 계산하기
      • bfs로 탐색하기

  • 글로벌 변수

    1. 먹은 물고기 수
      • 상어 성장 여부 판단
    2. 상어 크기
    3. 상어 위치
    4. 시간

  • 순차 로직

    1. 상어 위치 찾기
    2. bfs탐색하며 왼 위 아래 오른쪽 순 돌기
    3. 가장 먼저 탐색 된 상어 크기보다 작은 물고기 섭취
      • 물고기 섭취 불가시 종료
    4. 상어 성장 여부 판단
    5. 이동 시간 기록
    6. 1 - 4 반복

  • 코드

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

    INF = 1e9
ate_count = 0
shark_size = 2
shark_pos = []
happy_time = 0
directions = [
    [-1, 0],
    [0, -1],
    [1,0],
    [0, 1],
]

for i in range(n):
    for j in range(n):
        if n_space[i][j] == 9:
            shark_pos = [i,j]
            n_space[i][j] = 0


def bfs(x,y):
    global n, shark_size,n_space
    queue = deque()
    queue.append([x,y])
    visited = [[-1] * n for _ in range(n)]
    visited[x][y] = 0

    while len(queue) > 0:
        cur_x, cur_y = queue.popleft()

        for i in range(4):
            nx = cur_x + directions[i][0]
            ny = cur_y + directions[i][1]

            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if n_space[nx][ny] > shark_size:
                continue
            if visited[nx][ny] != -1:
                continue

            visited[nx][ny] = visited[cur_x][cur_y] + 1
            queue.append([nx,ny])
    return visited

def checkMin(visited):
    global shark_size

    x,y = 0, 0
    min_distance = INF
    for i in range(n):
        for j in range(n):
            if visited[i][j] == -1:
                continue
            if n_space[i][j] == 0 or n_space[i][j] >= shark_size:
                continue
            if visited[i][j] >= min_distance:
                continue
            min_distance = visited[i][j]
            x, y = i, j

    if min_distance == INF:
        return False

    return x, y, min_distance


while(True):
    result = checkMin(bfs(shark_pos[0], shark_pos[1]))
    if result == False:
        break;

    nx,ny,time = result

    shark_pos = [nx, ny]
    happy_time += time

    ate_count += 1
    n_space[nx][ny] = 0

    if ate_count == shark_size:
        shark_size += 1
        ate_count = 0

print(happy_time)

놓친 점

  1. 시간 복잡도를 계산하지 않았다.
  2. 가장 위/왼쪽이 순회를 통해 탐색이 가능할 것이라 생각했다.
    1. 가다 막히는 경우가 있기 때문에 항상 마름모꼴로 시간이 상승하지 않음을 간과했다.