백준 16236 파이썬

from _collections import deque

n = int(input())

data = [list(map(int, input().split())) for _ in range(n)]
shark_size = 2
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
cnt = 0
size_count = 0


def search_fish():
    result = n ** 3
    nx, ny = 0, 0
    global cnt
    global shark_size
    global shark_point
    global size_count

for i in range(n):
    for j in range(n):
        if data[i][j] != 0:
            if data[i][j] < shark_size:
                move_size = bfs(i, j)

                if result > move_size:
                    result = move_size
                    nx, ny = i, j

    if result == n ** 3:
        return False
    else:
        cnt += result
        size_count += 1
        if size_count == shark_size:
            size_count = 0
            shark_size += 1
        data[nx][ny] = 0
        shark_point = (nx, ny)
        return True


# 해당 지점까지 길이 구하기.
def bfs(point_x, point_y):
    shark_x, shark_y = shark_point
    visited = [[0 for _ in range(n)] for _ in range(n)]

    q = deque()
    q.append((shark_x, shark_y))
    while q:
    px, py = q.popleft()

    if px == point_x and py == point_y:
        data[shark_x][shark_y] = 0
        return visited[px][py]

    for i in range(4):
        nx, ny = px + dx[i], py + dy[i]
        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and data[nx][ny] <= shark_size:
            visited[nx][ny] = visited[px][py] + 1
            q.append((nx, ny))

    return n ** 3


shark_point = (0, 0)

for i in range(n):
    for j in range(n):
        if data[i][j] == 9:
            shark_point = (i, j)

while True:
    if search_fish() == False:
        print(cnt)
        break

위 코드는 문제의 정답 코드이다.

 

나는 이 문제를 풀려고 접근할 때, 두 가지 요소 생각을 했다.

1. 물고기 찾기.

2. 거리가 가까운 거 먹기.

 

search_fish()함수는: 먹을 수 있는 물고리를 전부 찾은 후, 그 중에서 가장 짧은 것을 선택하여 그 거리를 계산하여 먹는 것 까지이다.

우선 문제에서 같은 거리 상에 있다면 가장 위, 그리고 가장 왼쪽이 우선순위라고 했다.

이 말에서 중첩 for문을 쓸 때, 맨 위이고, 맨 왼쪽부터 차례로 내려오니까 이걸 사용하면 되겠다 싶었다.

 

bfs(point_x, point_y)함수는 상어가 point_x, point_y까지 먹으러 가는데 까지의 이동거리를 계산해 주는 것이다.

이 부분에서 의구심이 들만 한 부분들.

1. visited[nx][ny] == 0이거빼주면안되나?

visited[nx][ny] == 0 이 부분을 사용하는 이유는, 굳이 돌아서 가는 걸 세어줄 필요가 없기 때문이다.

직접 그림을 그려 보았을 때, 이미 방문한 visited[nx][ny]를 다시 방문할 경우는 돌아가거나 or 길이가 같은 경우 뿐이기 때문이다.

그리고 visited[nx][ny] == 0 이걸 빼줄 경우, 시간초과가 날 것이다.

왜냐면 굳이 돌아가는 것 까지 다 구해주니 시간초과가 날 수 밖에 없다. ( 빼줘도 답을 구하는 데에는 지장이 없긴하다.)

테스트 해보았더니 시간초과가 났다.

 

 

for i in range(n):
    for j in range(n):
        if data[i][j] != 0:
            if data[i][j] < shark_size:
                move_size = bfs(i, j)

                if result > move_size:
                    result = move_size
                    nx, ny = i, j

이 부분이 다른 풀이랑 조금 다른 점 일 수도 있다는 생각이 든다.

이 코드는 "같은 길이라면 그 중 맨위 and 맨 왼쪽"이 고려된 것이다.

중첩 for문으로 맨 위, 맨 왼쪽부터 차례로 내려오기 때문에, result > move_size로 크기가 만약 같더라도 >= 을 하지 않고, > 를 사용했기 떄문에 맨위, 맨 왼쪽이 먼저 들어가서 우선순위가 고려된 것이다.

 

 

이런 과정을 거쳐서 아기 상어가 먹을 수 있는 물고기 자표를 우선순위를 고려하여 구한다.

 

    if result == n ** 3:
        return False
    else:
        cnt += result
        size_count += 1
        if size_count == shark_size:
            size_count = 0
            shark_size += 1
        data[nx][ny] = 0
        shark_point = (nx, ny)
        return True

 

이 후 구한 값이 있다면 else문을 실행하고, 없다면 if문을 실행하여 더 이상 먹을 수 있는 물고기가 없음을 나타내준다.

왜 굳이 result == n ** 3 이렇게 했냐면,, 아무리 길어도 저것보단 길 수 없기 떄문에..저렇게 한 것인데, 이건 좀 비효율적이고 이상한 것 같다..

 

무튼 이렇게 해서 search_fish(), bfs() 두 함수를 구현하여 문제를 풀었다.