[백준] 16236번 (python 파이썬)

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

 

 

bfs, 구현 문제이다.

 

여기서 고려할점은

더 이상 먹을 수 있는 물고기가 공간에 없다.

  1. 상어보다 작은 물고기는 있지만 도달할 수 없다.

  2. 상어보다 작은 물고기가 없다.

  3. 모든 물고기를 먹어서 더이상 먹을 수 있는 물고기가 공간에 없다.

 

1. bfs를 돌렸을때 나온 거리가 INF이면 종료하였다.

n_x, n_y, dist, idx = bfs(c_x, c_y, small_fish, size)
if dist == math.inf:
	break

2. 상어보다 작은 물고기를 넣어논 list에 더이상 물고기가 없을 경우 종료하였다.

if len(small_fish) == 0:  # 끝
	return time

3. 물고기를 넣어논 list에 더이상 물고기가 없을 경우 종료하였다.

while fish:
 .
 .
 .

 

 

먹을수 있는 물고기가 있다.

bfs를 돌려서 상어보다 작은 물고기까지 도달할 수 있느 거리를 구한다.

상어보다 작은 물고기를 넣어놓은 list를 확인하면서 가장작은 거리를 구한다.

거리가 같을경우 좌표를 확인한다.

   x가 제일 작은 좌표:

      y가 제일 작은 좌표:

 

 

최종 코드

import math
from collections import deque

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

d_x = [-1, 0, 1, 0]
d_y = [0, 1, 0, -1]

for i in range(n):
    for j in range(n):
        if graph[i][j] != 0 and graph[i][j] != 9:
            fish.append((i, j, graph[i][j]))
        if graph[i][j] == 9:
            c_x, c_y = i, j


def solve(c_x, c_y):
    size = 2
    time = 0
    eat = 0
    if not fish:
        return time

    while fish:
        small_fish = list()
        i = 0
        for n_x, n_y, fish_size in fish:
            if fish_size < size:
                small_fish.append([n_x, n_y, graph[n_x][n_y], i])
            i += 1

        if len(small_fish) == 0:  # 끝
            return time
        else:  # 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
            n_x, n_y, dist, idx = bfs(c_x, c_y, small_fish, size)
            if dist == math.inf:
                break
            graph[n_x][n_y] = 9
            graph[c_x][c_y] = 0
            c_x, c_y = n_x, n_y
            fish.pop(idx)
            eat += 1
            time += dist

        if eat == size:
            size += 1
            eat = 0

    return time


def bfs(c_x, c_y, small_fish: list, size):
    visited = [[-1] * n for _ in range(n)]
    visited[c_x][c_y] = 0

    queue = deque()
    queue.append((c_x, c_y))

    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            n_x, n_y = pop_x + d_x[i], pop_y + d_y[i]

            if n_x < 0 or n_x >= n or n_y < 0 or n_y >= n or graph[n_x][n_y] > size:
                continue

            if visited[n_x][n_y] != -1:
                continue

            queue.append((n_x, n_y))
            visited[n_x][n_y] = visited[pop_x][pop_y] + 1

    min_dist = math.inf
    min_idx = math.inf
    min_x = math.inf
    min_y = math.inf
    for i in range(len(small_fish)):
        x, y, small_size, idx = small_fish[i]
        if visited[x][y] == -1:
            continue
        if visited[x][y] <= min_dist:
            if visited[x][y] == min_dist:
                if x <= min_x:
                    if x == min_x:
                        if y < min_y:
                            min_dist = visited[x][y]
                            min_x, min_y = x, y
                            min_idx = idx
                            continue
                        continue
                    continue
                continue

            min_dist = visited[x][y]
            min_x, min_y = x, y
            min_idx = idx

    return min_x, min_y, min_dist, min_idx


print(solve(c_x, c_y))

 

 

• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이 조건때문에 

 min_dist = math.inf
    min_idx = math.inf
    min_x = math.inf
    min_y = math.inf
    for i in range(len(small_fish)):
        x, y, small_size, idx = small_fish[i]
        if visited[x][y] == -1:
            continue
        if visited[x][y] <= min_dist:
            if visited[x][y] == min_dist:
                if x <= min_x:
                    if x == min_x:
                        if y < min_y:
                            min_dist = visited[x][y]
                            min_x, min_y = x, y
                            min_idx = idx
                            continue
                        continue
                    continue
                continue

            min_dist = visited[x][y]
            min_x, min_y = x, y
            min_idx = idx

이 식을 사용했는데

 

min heap 을 사용하면 더욱 간단하게 풀 수 있다는 것을 알았다.

 

import heapq

test = list()
heapq.heappush(test, [7,3,4])
heapq.heappush(test, [2,3,4])
heapq.heappush(test, [2,3,2])
heapq.heappush(test, [4,3,4])
heapq.heappush(test, [5,3,4])
heapq.heappush(test, [6,3,4])

print(heapq.heappop(test))
print(heapq.heappop(test))
print(heapq.heappop(test))
print(heapq.heappop(test))

#######결과#########3
[2, 3, 2]
[2, 3, 4]
[4, 3, 4]
[5, 3, 4]

여기서 0: 거리, 1: x, 2: y라고 한다면 알아서 작은 순서로 뽑힌다. 처음에 0비교 그 다음 1비교 그 다음 2비교

 

 

수정 코드

 

import heapq
from collections import deque

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

d_x = [-1, 0, 1, 0]
d_y = [0, 1, 0, -1]

for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            c_x, c_y = i, j


def solve(c_x, c_y):
    size = 2
    time = 0
    eat = 0

    while True:
        # 먹을 수 있는 물고기가 있으면 그 물고기를 먹으러 간다.
        heap = bfs(c_x, c_y, size)
        if not heap:
            break
        dist, n_x, n_y = heapq.heappop(heap)
        graph[n_x][n_y] = 9
        graph[c_x][c_y] = 0
        c_x, c_y = n_x, n_y
        eat += 1
        time += dist

        if eat == size:
            size += 1
            eat = 0

    return time


def bfs(c_x, c_y, size):
    visited = [[-1] * n for _ in range(n)]
    visited[c_x][c_y] = 0

    queue = deque()
    queue.append((c_x, c_y))
    heap = list()

    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            n_x, n_y = pop_x + d_x[i], pop_y + d_y[i]

            if n_x < 0 or n_x >= n or n_y < 0 or n_y >= n or graph[n_x][n_y] > size:
                continue

            if visited[n_x][n_y] != -1:
                continue

            queue.append((n_x, n_y))
            visited[n_x][n_y] = visited[pop_x][pop_y] + 1
            if 0 < graph[n_x][n_y] < size:
                heapq.heappush(heap, [visited[n_x][n_y], n_x, n_y])

    return heap


print(solve(c_x, c_y))