125. [삼성기출21]Python 백준 16236 번 아기상어

안녕하세요 코딩하는 덕구입니다.

백준 16236 번 아기상어 입니다.

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

16236번: 아기 상어

 

먼저 백준 16236 번 아기상어 코드입니다. 설명은 아래에 있습니다.

from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

candidate = []

def bfs(x, y):
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True
    queue = deque()
    queue.append([x, y, 0])
    candidate = []
    if board[x][y] == 9:
        board[x][y] = 0
    limit_time = 9999

    while queue:
        x, y, time = queue.popleft()
        if time < limit_time:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if not visited[nx][ny]:
                        if board[nx][ny] == 0 or board[nx][ny] == shark_size:
                            visited[nx][ny] = True
                            queue.append([nx, ny, time + 1])

                        elif board[nx][ny] < shark_size:
                            visited[nx][ny] = True

                            candidate.append([nx, ny, time + 1])
                            limit_time = time + 1
    return candidate

exp = 0
total_time = 0
shark_size = 2

for i in range(N):
    for j in range(N):
        if board[i][j] == 9:
            x = i
            y = j

while True:
    candidate = bfs(x, y)
    if len(candidate) == 0:
        break

    candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
    x, y, time = candidate[0]#맨앞 후보 잡아먹기
    board[x][y] = 9
    exp += 1

    if exp == shark_size: #상어 성장
        shark_size += 1
        exp = 0
    total_time += time

print(total_time)

 

문제 접근

1. bfs를 통해 가까운 거리의 먹을 수 있는 물고기를 탐색합니다.

2. 조건에 맞는 물고기를 먹고 그 자리에서 다시 bfs를 반복합니다.

 

Python 코드 구현

bfs에 필요한 변수들을 선언합니다.

 

from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

candidate = []

 

맨 처음 상어의 위치를 찾고, 해당 위치부터 bfs를 실행합니다.

bfs는 가까운 먹이감들의 좌표, 거리를 담는 리스트를 return합니다.

bfs 실행 후 먹이를 먹는 순서로 리스트를 정렬하고, 먹이를 먹습니다.

또한 성장조건이 된다면 상어는 성장합니다.

먹을 수 있는 물고기가 없을때 까지 반복하고 답을 출력하면 됩니다.

exp = 0
total_time = 0
shark_size = 2

for i in range(N):
    for j in range(N):
        if board[i][j] == 9:
            x = i
            y = j

while True:
    candidate = bfs(x, y)
    if len(candidate) == 0:
        break

    candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
    x, y, time = candidate[0]#맨앞 후보 잡아먹기
    board[x][y] = 9
    exp += 1

    if exp == shark_size: #상어 성장
        shark_size += 1
        exp = 0
    total_time += time

print(total_time)

 

bfs는 두가지 조건이 있습니다. 

먹을 수 있는가, 없는가

만약 먹을 수 있다면 후보 리스트에 추가합니다.

먹을 수 없고, 지나갈 수 있다면 해당 위치에서 다시 탐색합니다.

이때 후보 리스트에 있는 먹있감보다 거리가 멀어지면 탐색하지 않습니다.

def bfs(x, y):
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True
    queue = deque()
    queue.append([x, y, 0])
    candidate = []
    if board[x][y] == 9:
        board[x][y] = 0
    limit_time = 9999

    while queue:
        x, y, time = queue.popleft()
        if time < limit_time:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if not visited[nx][ny]:
                        if board[nx][ny] == 0 or board[nx][ny] == shark_size:
                            visited[nx][ny] = True
                            queue.append([nx, ny, time + 1])

                        elif board[nx][ny] < shark_size:
                            visited[nx][ny] = True

                            candidate.append([nx, ny, time + 1])
                            limit_time = time + 1
    return candidate

 

파이썬 백준 16236 번 아기상어 최종 코드입니다. 

from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

candidate = []
            
def bfs(x, y):
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True
    queue = deque()
    queue.append([x, y, 0])
    candidate = []
    if board[x][y] == 9:
        board[x][y] = 0
    limit_time = 9999

    while queue:
        x, y, time = queue.popleft()
        if time < limit_time:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if not visited[nx][ny]:
                        if board[nx][ny] == 0 or board[nx][ny] == shark_size:
                            visited[nx][ny] = True
                            queue.append([nx, ny, time + 1])

                        elif board[nx][ny] < shark_size:
                            visited[nx][ny] = True

                            candidate.append([nx, ny, time + 1])
                            limit_time = time + 1
    return candidate

exp = 0
total_time = 0
shark_size = 2

for i in range(N):
    for j in range(N):
        if board[i][j] == 9:
            x = i
            y = j
            
while True:
    candidate = bfs(x, y)
    if len(candidate) == 0:
        break

    candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
    x, y, time = candidate[0]#맨앞 후보 잡아먹기
    board[x][y] = 9
    exp += 1

    if exp == shark_size: #상어 성장
        shark_size += 1
        exp = 0
    total_time += time

print(total_time)

 

백준 16236 번 아기상어 Python 코드였습니다.

감사합니다.