[백준 16236번-아기상어]-파이썬

solved.ac 난이도 :  Gold3

백준    16236번- 파이썬 풀이

 

<문제>

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

16236번: 아기 상어

<풀이>-구현,시뮬레이션,BFS

이 문제는 생각만 충분히 해본다면 크게 어렵지는 않은 문제인거 같다. 이문제를 풀기위해 가장 중요한것은 우선 문제에서 제시한 조건들을 꼼꼼히 읽어 실수를 없애는 것이고 물고기를 찾는 함수, 각각의 위치까지의 최단거리를 구하는 함수를 따로따로 구현해 줘야 한다는 것이다. 그렇다면 이 두함수를 어떻게 구현하였는지 한번 천천히 살펴보자

 

-각각의 위치까지의 최단거리를 구하는 함수-

 

이 문제에서 최단거리란  아기상어가 이동이 가능한 위치까지의 최단거리를 의미한다.

 

따라서 아기상어가 현재 위치한곳의 좌표를 큐에 삽입하고 인접한 네방향이 문제에서 제시한 조건을 만족하는지 살펴본다.

 

조건들을 모두 만족한다면 큐에 삽입하고 현재 위치에서 한칸 떨어진 위치기 때문에 거리를 저장하는 배열에서 해당위치에 +1을 해주면 된다. 

 

거리를 저장하는 배열은 우선 dist = [[-1]*n for _ in range(n)]으로 초기화 한다. 0으로 초기화 하지 않는 이유는 처음 아기상어의 위치를 최단거리 0으로 보고자 함이기 때문이다. 

#모든 위치까지의 최단거리만 계산

def bfs():
    dist = [[-1]*n for _ in range(n)]
    queue = deque([(now_x,now_y)])
    dist[now_x][now_y] = 0
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if array[nx][ny]<=now_size and dist[nx][ny] == -1:
                    queue.append((nx,ny))
                    dist[nx][ny] = dist[x][y]+1
    return dist

-먹을 물고리를 찾는 함수-

 

이 부분에서 실수하기 쉬울거 같다. 우선 아기상어는 현재위치에서 "가장 가까운 거리의 물고기"만 먹는다고 했다.

 

그렇다면 가장 가까운 물고기의 위치를 구하고 아기상어의 현재위치를 갱신해 주어야 한다.

 

이때 가장 가까운 거리를 구하기위해서는 물고기까지의 거리와 현재의 최단거리를 비교해주는 과정이 필요한다.

 

이러한 과정을 위해 INF = 1e9 라는 값을 설정해주고 이 값을 초기 최단거리로 설정한다. 그 다음 물고기까지의 거리와 비교해 계속해서 최단거리의 물고기를 찾으면 된다. 

 

만약 최단거리가 갱신되지 않고 계속 INF 라면 더이상 먹을 물고기가 존재하지 않음을 의미한다. 이럴경우 None을 반환하고 그렇지 않다면 최단거리의 위치와 최단거리(즉 그 위치까지 이동하는데 걸리는 시간)을 반환한다.

 

def find(dist):
    x,y = 0,0
    min_dist = INF
    for i in range(n):
        for j in range(n):
            if dist[i][j]!=-1 and 1<=array[i][j]<now_size:
                if dist[i][j]<min_dist:
                    x,y = i,j
                    min_dist = dist[i][j]
    if min_dist == INF: #먹을 물고기가 없는 경우
        return None
    else:
        return x,y,min_dist

728x90

반응형

<코드>-파이썬

from collections import deque

INF = 1e9 #최단거리 계산할때 사용

n = int(input())

array = []

for i in range(n):
    array.append(list(map(int,input().split())))

now_size = 2
now_x,now_y = 0,0

for i in range(n):
    for j in range(n):
        if array[i][j] == 9:
            now_x,now_y = i,j
            array[now_x][now_y] = 0

dx = [-1,0,1,0]
dy = [0,-1,0,1]

#모든 위치까지의 최단거리만 계산

def bfs():
    dist = [[-1]*n for _ in range(n)]
    queue = deque([(now_x,now_y)])
    dist[now_x][now_y] = 0
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if array[nx][ny]<=now_size and dist[nx][ny] == -1:
                    queue.append((nx,ny))
                    dist[nx][ny] = dist[x][y]+1
    return dist

def find(dist):
    x,y = 0,0
    min_dist = INF
    for i in range(n):
        for j in range(n):
            if dist[i][j]!=-1 and 1<=array[i][j]<now_size:
                if dist[i][j]<min_dist:
                    x,y = i,j
                    min_dist = dist[i][j]
    if min_dist == INF: #먹을 물고기가 없는 경우
        return None
    else:
        return x,y,min_dist
result  = 0
ate = 0
while True:
    value = find(bfs())
    if value == None:
        print(result)
        break
    else:
        now_x,now_y = value[0],value[1]
        result+=value[2]
        array[now_x][now_y] = 0
        ate+=1
    if ate>=now_size:
        now_size+=1
        ate = 0

-while문 부분 설명-

 

더이상 먹을 물고기가 존재하지 않을 때 까지 반복한다.

 

만약 find(bfs())를 한 결과 반환값이 주어진다면 아기상어의 현재위치를 반환값으로 갱신하고 result 변수에 현재 아기상어가 이동한 최단거리, 즉 이동한 시간을 저장한다.

 

그리고 문제의 조건에서 자신의 크기와 먹은 물고기의 갯수가 같아질 경우 사이즈가 1증가한다 했으므로 ate변수에 +1을 해주고 ate가 now_size와 같아지면 now_size에도 +1을 해준다.

 

-마치며-

역시 삼성전자 기출문제라 그런지 상당히 문제를 처음 접했을땐 많이 어렵다는 느낌을 받았다. 그래서 한참동안 해매다가 결국, 책의 도움을 약간 받았다. 책에서 세부적으로 함수를 나눠서 구현한 것을 보고 그때부터는 수월하게 문제를 풀었던거 같다.