[백준 16236] 아기 상어

1. 문제

 

www.acmicpc.net/problem/16236

16236번: 아기 상어

2. 접근방법

 

1. 상어의 위치를 구한다

2. BFS를 이용해서 순회한다

  2-1. 이 때, 상어가 움직일 수 있는 좌표를 담은 queue(q), 먹을 수 있는 물고기를 담은 queue(eatq) 이렇게 두 개가 필요하다

  2-2. 먹을 수 있는 물고기 기준인 상어의 크기를 변수로 만든다. (level)

  2-3. 상어가 이동한 거리를 담을 변수를 만들어준다. (eat_time)

  2-4. 상어가 먹은 물고기 갯수를 담을 변수를 만들어준다. (eat_num)

3. 무한 루프를 이용한다. (while True)

  3-0. 무한 루프는 상어가 한마리의 물고기를 먹을 때까지의 루프이다.

  3-1. 따라서 무한루프의 break 조건은 먹을 물고기가 없을 때 (문제에 나온 조건임, 먹을 물고기 존재 유무는 boolean값으로 만들어서 확인)

  3-2. 무한 루프에서 방문 체크를 해준다. (visited)

    3-2-1. 왜냐하면, 한 마리를 먹기 위해 움직일 때 동선이 겹치면 안되기 때문. 한 마리 먹고 나서는 그 전에 갔던 곳 다시 가도 됨

  3-3. 현재 상어의 위치에 물고기가 존재하는 경우 !! => 바로 먹지 않고, 먹을 수 있는 물고기인지 확인(level 확인) 후 먹을 수 있는 물고기를 담은 queue에 담아준다. (이 때, 물고기까지의 거리인 cnt도 함께 담아준다.)

  3-4. 현재 상어의 위치에 물고기가 존재하지 않는 경우 !! => 4방 탐색을 통해 상어가 움직일 수 있는 좌표를 queue에 담아준다. (이 때, 거리를 의미하는 cnt도 함께 담아준다, cnt의 경우 현재 cnt에서 +1한 값)

 

  3-5. break는 여기서 해준다. (상어 이동 queue(q)가 끝났을 때)

 

  3-6. eatq를 하나씩 확인한다.

    3-6-0. 먹을 물고기를 선정해야하기 때문에, 선정을 위한 변수를 지정한다. (min_cnt, min_x, min_y) : 거리, 좌표x, 좌표y

    3-6-1. 만약 거리(cnt)가 min_cnt보다 작다면 -> 해당하는 좌표 값과 cnt으로 갱신한다.

    3-6-2. min_cnt와 거리가 같다면 -> 해당 좌표에서 y값이 더 작은지 확인 -> 작다면 갱신

    3-6-3. min_cnt와 거리도 같고, y좌표 값도 같다면 -> x값 기준으로 왼쪽에 있는지 확인 -> 왼쪽에 있다면 갱신

  3-7. 먹을 물고기가 있다면 물고기를 먹고, eat_time 을 증가시키고, eat_num(먹은 물고기 갯수)도 +1하고 이에 따라 level도 갱신해준다.(갱신 여부는 eat_num 기준) 그리고 현재 상어 위치를 해당 물고기 위치로 갱신하고 다시 q에 집어 넣어서 무한루프 시작 ~!

 

3. 파이썬 코드

 

from collections import deque

def bfs(x, y):
    global N
    dir = [[0, -1], [-1, 0], [1, 0], [0, 1]]
    q = deque()
    q.append((x, y, 0))

    eatq = deque()

    eat_time = 0
    eat_num = 0

    level = 2

    min_x = x
    min_y = y

    while True:
        eat = False
        visited = [[False] * N for _ in range(N)]
        visited[min_y][min_x] = True
        while q:
            now_x, now_y, cnt = q.popleft()
            if board[now_y][now_x] == 9:
                board[now_y][now_x] = 0

            if board[now_y][now_x] != 0 and board[now_y][now_x] < level:
                eat = True
                eatq.append((now_x, now_y, cnt))
                while q:
                    test_x, test_y, cnt = q.popleft()
                    if board[test_y][test_x] != 0 and board[test_y][test_x] < level:
                        eatq.append((test_x, test_y, cnt))
            else:
                for i in range(4):
                    test_x = now_x + dir[i][0]
                    test_y = now_y + dir[i][1]
                    if 0 <= test_x < N and 0 <= test_y < N and visited[test_y][test_x] == False and board[test_y][test_x] <= level:
                        visited[test_y][test_x] = True
                        q.append((test_x, test_y, cnt+1))

        if not eat:
            break

        min_x = -1
        min_y = -1
        min_cnt = 1e9

        while eatq:
            eat_x, eat_y, eat_cnt = eatq.popleft()
            if eat_cnt < min_cnt:
                min_cnt = eat_cnt
                min_x = eat_x
                min_y = eat_y

            elif eat_cnt == min_cnt:
                if eat_y < min_y:
                    min_cnt = eat_cnt
                    min_x = eat_x
                    min_y = eat_y

                elif eat_y == min_y:
                    if eat_x < min_x:
                        min_cnt = eat_cnt
                        min_x = eat_x
                        min_y = eat_y

        if min_x != -1:
            board[min_y][min_x] = 0
            eat_time += min_cnt
            eat_num += 1
            if eat_num == level:
                eat_num = 0
                level += 1
            q.append((min_x, min_y, 0))

    return eat_time

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0

for y in range(N):
    for x in range(N):
        if board[y][x] == 9:
            start_x, start_y = x, y

print(bfs(start_x, start_y))

 

 

4. 마치며

 

어제부터 어떻게 접근해야할지 몰라 고민한 문제인데 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!첫 시뮬 문제 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!여서 힘들었는데 !!!!!!!!!!!!!!!!!!!사실 처음에 그냥 BFS 이용해서 그냥 물고기 막 먹었는데 예제 4에서 나가리 되어가지고 ..잘못 접근한 것을 깨닫고 ..갓 승환님과 갓 하늘님의 도움으로 한땀한땀 정성스레 만든 코드입니다요

 

시험은 내일인데 . . . . 아니 12시간 뒤 . . . .인데 .. .  . 코드를 느껴보고자 바로 포스팅했슴다

 

약간 지금은 덜 정제되었지만 내일 다시 읽어보고 정제하는 과정을 거쳐보도록 합죠

 

www.youtube.com/watch?v=761ae_KDg_Q