[BOJ] 16236 - 아기상어

김우경·2021년 4월 23일

삼성기출

목록 보기

26/37

문제 링크

문제 설명

N*N 크기의 공간에 물고기 M마리와 아기상어 1마리가 있다. 한칸에는 최대 물고기 1마리가 있다. 물고기와 아기 상어는 각각 크기를 가지고, 아기 상어의 초기 크기는 2, 1초마다 상하좌우 이동한다.
나보다 큰 물고기가 없는 칸으로 이동이 가능하고, 나보다 작은 물고기만 먹을 수 있다. 더이상 먹을 물고기가 없으면 종료되고, 1마리면 해당 물고기가 있는 칸, 먹을 수 있는 물고기가 1마리 이상이면 제일 가까운 물고기를 먹는다. 이때 거리는 아기상어부터 물고기까지의 칸 개수를 의미한다. 거리가 가까운 물고기가 여러마리면 가장 위에 있고 가장 왼쪽에 있는 물고기를 먹는다. 아기상어는 자기 크기만큼 물고기를 먹으면 크기가 1증가한다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 물고기를 잡아먹을 수 있는지 구하세요

문제 풀이

입력받기

board[i][j] : (i,j) 칸에 있는 물고기의 크기 저장
shark = [i,j] : 상어의 현재 좌표 [i,j] 저장

N = int(input())
board = []
shark = []
shark_weight = 2
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] == 9:
            shark = [i,j]
    board.append(tmp)
board[shark[0]][shark[1]] = 0

상어 이동시키기

find() 함수를 이용해서 아기상어가 먹을 수 있는 가장 가까운 물고기의 좌표를 구한다.

time = 0
eat = 0
while True:
    # 상어 이동하기
    count, x, y = find(shark, i)

    if count == -1:
        # 더 먹을 물고기 x
        break
    
    board[x][y] = 0
    shark = [x, y]
    eat += 1
    if eat == shark_weight:
        shark_weight += 1
        eat = 0
    time += count

print(time)

아기상어가 먹을 수 있는 가장 가까운 물고기 좌표 구하기

bfs를 활용해서 구현하였다.

시도 1

queue에 [현재까지 이동한 x좌표, y좌표, 이동 칸수, 이동 경로]를 넣었다.

def find(shark, d):
    visit = [[0 for _ in range(N)] for _ in range(N)]
    visit[shark[0]][shark[1]] = 1
    queue = deque([[shark[0], shark[1], 1, visit]])
    min_count, n_x, n_y = float('INF'), 0, 0
    
    while queue:
        x, y, count, visited = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny) and visited[nx][ny] == 0:
                if board[nx][ny] != 0 and board[nx][ny] < shark_weight:
                    # 작으면 이 물고기 먹기
                    if count < min_count:
                        min_count = count
                        n_x, n_y = nx, ny
                    elif count == min_count:
                        if n_x > nx:
                            n_x, n_y = nx, ny
                        elif n_x == nx and n_y > ny:
                            n_x, n_y = nx, ny
                elif board[nx][ny] == 0 or board[nx][ny] == shark_weight:
                    # 이동가능하면 이동
                    visited[nx][ny] = 1
                    queue.append([nx,ny,count+1, visited])

    if min_count != float('inf'):
        return min_count, n_x, n_y            
    else:
        return -1, -1, -1

통과는 되는데 메모리를 너무 많이 잡아먹어서 정답이 아니라고 생각했다.

시도 2

홍익대 백준 9등 선생님께 ㅋㅋ 도움 요청
queue에 count나 이동 경로를 따로 저장하지 말고, inf로 초기화된 visited 배열에 count를 저장했다.

def find(shark, d):
    visited = [[float('INF') for _ in range(N)] for _ in range(N)]
    queue = deque([[shark[0], shark[1]]])
    visited[shark[0]][shark[1]] = 0
    min_count, n_x, n_y = float('INF'), 0, 0
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny) and visited[x][y]+1 < visited[nx][ny]:
                if board[nx][ny] != 0 and board[nx][ny] < shark_weight:
                    # 작으면 이 물고기 먹기
                    if visited[x][y]+1 < min_count:
                        min_count = visited[x][y]+1
                        n_x, n_y = nx, ny
                        visited[nx][ny] = visited[x][y]+1
                    elif visited[x][y]+1 == min_count:
                        if n_x > nx:
                            n_x, n_y = nx, ny
                            visited[nx][ny] = visited[x][y]+1
                        elif n_x == nx and n_y > ny:
                            n_x, n_y = nx, ny
                            visited[nx][ny] = visited[x][y]+1
                elif board[nx][ny] == 0 or board[nx][ny] == shark_weight:
                    # 이동가능하면 이동
                    if visited[x][y]+1 < min_count:
                        visited[nx][ny] = visited[x][y] + 1
                        queue.append([nx,ny])

    if min_count != float('inf'):
        return min_count, n_x, n_y            
    else:
        return -1, -1, -1