[백준] 16236_아기상어 (Python)

16236_아기상어 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 16236번: 아기상어

1. 기록

• 22/07/05 (화)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 상어의 위치를 찾고
>> 가장 가까운 거리의 물고리를 찾을때 visited 배열을 이용한다.
>> 가장 가까운 거리의 물고기를 찾는다. dfs() 이용

>> 이동 가능여부 판단 함수를 만든다                                                  ---- 종료조건 ★
>> graph 에 있는 숫자가 0 또는 size 보다 큰 경우 더 이상 먹을 수 있는 먹이가 없다.
>> graph 에 있는 숫자가 0 또는 size 작은경우 먹을 수 있는 먹이가 있다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
0 0 0
0 0 0
0 9 0

- 예제 출력 1 -
0

- 예제 입력 2 -
3
0 0 1
0 0 0
0 9 0

- 예제 출력 2 -
3

- 예제 입력 3 -
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

- 예제 출력 3 -
14

- 예제 입력 4 -
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

- 예제 출력 4 -
60

- 예제 입력 5 -
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1

- 예제 출력 5 -
48

- 예제 입력 6 -
6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9

- 예제 출력 6 -
39

- 반례 케이스 1 -
3
0 1 1
4 4 4
0 9 0

- 출력 1 -
0

- 반례 케이스 2 -
3
0 1 1
4 4 4
1 9 0

- 출력 1 -
1

- 반례 케이스 3 -
20
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 9

- 출력 3 -
0

- 출력 -
0

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

n = int(input())

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

size = 2
feed = 0
dist = 0
check3 = 0

# fixme - 최초 상어의 위치를 찾는다.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            sx = i
            sy = j

# fixme - 더이상 먹을 수 있는 먹이가 없는 경우 종료시킨다.
def ending():
    flag = False

    for i in range(n):
        for j in range(n):
            # 자기 자신은 먹이가 아니므로 건너뛴다. 
            if graph[i][j] == 9:
                continue

            # 먹이를 찾은 경우
            elif graph[i][j] != 0 and graph[i][j] < size:
                flag = True

    return flag

# fixme - 먹이 먹을 곳을 찾자
def feeding(dist_check, feed, size):
    if len(dist_check) == 0:
        exit()
        return False

    dist_check = list(dist_check)
    dist_check.sort(key = lambda x:[x[2], x[0], x[1]])

    tx, ty, d = dist_check[0]

    feed += 1
    if feed == size:
        feed = 0
        size += 1

    return tx, ty, d, feed, size


def iterative_dfs(sx, sy, graph, dist, visited):

    global feed
    global size
    global check3

    feed = 0
    size = 2

    while ending():

        if check3 == 1:
            break

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

        q = deque([])
        q.append((sx, sy))

        graph[sx][sy] = 0

        dist_check = deque([])

        while q:
            x, y = q.popleft()
            min_dist = 10000000

            # fixme - 사방이 막혀있거나 이동할 수 없는 경우
            check1 = 0
            check2 = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    check1 += 1
                    if graph[nx][ny] > size:
                        check2 += 1

            if check1 == check2:
                check3 = 1
                break

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    # fixme - 먹이를 먹을 수 있는 경우 - 좌표와 거리만 체크해둔다.
                    if graph[nx][ny] != 0 and graph[nx][ny] < size:
                        if min_dist >= visited[x][y] + 1:
                            min_dist = visited[x][y] + 1
                            dist_check.append((nx, ny, visited[x][y] + 1))

                    # fixme - 이동만 가능한 경우
                    elif graph[nx][ny] == size or graph[nx][ny] == 0:
                        if visited[nx][ny] == 0:
                            q.append((nx, ny))
                            visited[nx][ny] += visited[x][y] + 1

                    # fixme - 먹이를 먹을 수 없는 경우
                    else:
                        visited[nx][ny] = -1

        if len(dist_check) >= 1:
            sx, sy, d, feed, size = feeding(dist_check, feed, size)
        elif len(dist_check) == 0:
            d = 0

        # fixme - 먹이를 먹을 수 있는 경로를 아무것도 못찾은 경우
        if d == 0 and dist == 0:
            return 0
        elif d == 0 and dist != 0:
            return dist

        dist += d

        # fixme - 재정비한다.
        graph[sx][sy] = 9
        visited = [[0 for _ in range(n)] for _ in range(n)]


    return dist

dist = iterative_dfs(sx, sy, graph, dist, visited)

print(dist)

(4) 정리

전에 풀어봤던 문제임에도 오래간만에 다시 푸는데 막히는 부분이 있었습니다.
참고 링크에 제가 막혔던 부분에 대해서 질문하고 답변받아 해결했습니다.

(5) 참고

질문 링크