[백준] 16236번 : 아기 상어 (파이썬)

BFS 문제 

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

16236번: 아기 상어

 

문제 조건

• 처음에 아기 상어의 크기는 2, 아기 상어는 상하좌우로 인접한 한 칸씩 이동
• 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지날 수 없고, 나머지 칸은 모두 지나갈 수 있다.
• 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

 

(1) 처음에 생각한 방식 (실패)

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = []
visited = [[False] * n for _ in range(n)]
time = [[0] * n for _ in range(n)]
print(visited)
startX = 0
startY = 0

for i in range(n):
    l = list(map(int, sys.stdin.readline().split()))
    graph.append(l)

    for j in range(n):
        if l[j] == 9:
            startY = i
            startX = j

def bfs(graph, startY, startX):
    dy = [-1, 0, 1, 0]
    dx = [0, -1, 0, 1]

    queue = deque()
    queue.append((0, startY, startX))
    visited[startY][startX] = True
    sharkSize = 2
    sharkCnt = 0
    totalTime = 0
    day = 0
    while queue:
        cnt, y, x = queue.popleft()
        count = cnt
        
        for i in range(4):
            nextX = x + dx[i]
            nextY = y + dy[i]
            print(nextY, nextX, count)

            if nextX >= 0 and nextX < n and nextY >=0 and nextY < n:
                if visited[nextY][nextX] == True: continue
                if graph[nextY][nextX] > sharkSize: continue

                if graph[nextY][nextX] < sharkSize: 
                    visited[nextY][nextX] = True
                    time[nextY][nextX] = time[y][x] + 1

                    if graph[nextY][nextX] != 0:
                        sharkCnt += 1
                        totalTime += count

                if sharkCnt == sharkSize:
                    sharkSize += 1
                    sharkCnt = 0
                queue.append((count + 1, nextY, nextX))

    print(count)
    return totalTime

count= bfs(graph, startY, startX)
print(count)
print(time)

 

▪︎ 조건에 맞게 수정한 부분

 

1) 한번에 하나의 물고기만 먹을 수 있다. 그래프 내에서 상어보다 크기가 작은 물고기가 존재할 때까지 계속 탐색해야 한다. 

위의 조건이 의미하는건 그래프 내에서 상어보다 크기가 작은 물고기가 존재할 때까지 계속 탐색해야 한다. 하지만, 한번에 하나의 물고기만 먹을 수 있기 때문에 현재 위치에서 최단거리이면서 가장 위쪽, 왼쪽에 있는 물고기를 찾았다면 해당 물고기를 먹고 해당 위치에서 Bfs를 다시 돌려야 한다. 그 이유는 예제 입력 3을 가지고 설명해보겠다.

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

 

 

처음 시작 좌표값 2,2(값: 9)에서 먹을 수 있는 최단거리, 가장 위쪽, 왼쪽 좌표인 0,3에 도달하여 물고기를 먹었다. 우리는 그 다음 먹을 수 있는 물고기를 탐색하기 위해 현재 좌표인 0,3에서 0,2 혹은 1,3으로 이동해야 한다. 하지만 처음 생각한 방식인 Bfs 한번만 도는 방향으로 구현시 queue를 사용하여 다음에 탐색할 좌표를 꺼내기 때문에 0,3 다음에 꺼내는 값을 출력해보면 0,1이란 좌표가 나온다. 즉, 처음 시작 좌표인 2,2(값: 9)을 기준으로 최단거리를 찾아 이동하기 때문에 이러한 값이 나올 수 밖에 없는 것이다.

그렇다면 어떻게 해야 할까 ? Bfs를 사용하면 안되는거 아니냐 ? 아니다.

최단거리, 가장 위쪽, 왼쪽 좌표의 물고기를 먹고 그 좌표를 시작 좌표로 Bfs를 다시 돌려 그 다음번에 먹을 (현재 좌표 기준으로 최단거리인) 물고기를 찾는다.

즉, 처음에 생각한 방식과 수정한 코드의 차이점은 아래와 같다.

 

• 처음에 생각한 방식 : 상어의 크기와 물고기의 크기를 비교해 먹을 수 있는 물고기를 처음 좌표(값: 9)만을 기준으로 찾아서 먹는다. (Bfs를 한번만 돌리기 때문)  
• 수정한 코드 : 상어의 크기와 물고기의 크기를 비교해 먹을 수 있는 물고기를 매번 갱신되는 시작 좌표를 기준으로 찾아서 먹는다. 이때, 이 시작좌표는 마지막으로 상어가 물고기를 먹은 위치를 의미한다. 따라서, Bfs를 매 시작좌표마다 돌려 현재 좌표를 기준으로 매번 최단거리를 찾아 먹는다.

def bfs(graph, startY, startX):
    global cntTotal, sharkSize, sharkCnt
    visited = [[False] * n for _ in range(n)] # 1) BFS 돌때마다 visited 배열 초기화
    
    visited[startY][startX] = True # 4) 시작 좌표 방문 처리 (이전 BFS에서 먹은 물고기 좌표)
    eat = sys.maxsize, startY, startX # 6) eat 초기좌표

    while queue:
        cnt, y, x = queue.popleft()

        for i in range(4):
            nextX = x + dx[i]
            nextY = y + dy[i]

            if 0 <= nextX < n and 0 <= nextY < n:
                if graph[nextY][nextX] > sharkSize or visited[nextY][nextX]: continue
                if 0 < graph[nextY][nextX] < sharkSize:

                    eat = min(eat, (cnt + 1, nextY, nextX))

                visited[nextY][nextX] = True # 5) visited 배열 방문 조건 변경
                queue.append((cnt + 1, nextY, nextX))

    return eat

graph[startY][startX] = 0 # 3) 처음 시작 좌표값 방문처리
while True:
    count, startY, startX = bfs(graph, startY, startX)
    if count == sys.maxsize: # 7) while문 탈출 조건 지정
        break
    graph[startY][startX] = 0 # 2) 이미 먹은 물고기 관리하기 위함.
    sharkCnt += 1
    cntTotal += count

    if sharkCnt == sharkSize:
        sharkSize += 1
        sharkCnt = 0

 

1. Bfs를 매번 돌리게 수정하였기 때문에, visited 배열도 Bfs를 돌릴 때마다 초기화해주었다.
2. 1에 따라 visited 배열이 매번 초기화되기 때문에 이미 방문해서 먹은 물고기 좌표를 따로 관리해주어야 한다. 처음에는 전역변수로 visitedList라는 리스트를 만들어 물고기를 먹고 나서 좌표값을 추가해주는 식으로 구현했다. 하지만, Bfs에서 좌표값을 방문할 때마다 해당 좌표값이 visitedList에 있는지 추가로 확인해줘야될뿐더러 해당 리스트를 위해 메모리가 추가적으로 필요하기 때문에 이 방법 대신 이미 방문해서 먹은 물고기 graph 값을 0으로 바꿔주는 방법을 사용하였다. graph 값이 0이라면 빈 칸이라고 인지할 것이기 때문이다. 
3. 제일 처음에 시작 좌표(값: 9)도 2와 같은 방식으로 방문처리를 해주어야한다. 시작좌표값 방문처리를 해주지 않으면 나중에 상어의 크기가 9보다 커졌을 때, 이 좌표를 물고기 좌표로 인지하고 먹을 수도 있기 때문이다.
4. 시작좌표를 방문처리해주는 부분이다. 이도 사실 2,3에서 graph의 시작좌표(값:9 / 이미 먹은 물고기 좌표)를 0으로 만들어주기 때문에 굳이 안써줘도 된다.
5. 이미 방문한 좌표가 아니거나 물고기 크기가 상어 크기보다 더 큰 경우가 아니라면 해당 좌표가 조건에 맞는지 검증하고 모두 방문 처리를 해주었다. 처음에 구현한 방식에서는 bfs를 한번만 돌리기 때문에 물고기의 크기가 상어의 크기보다 더 작은 경우에만 물고기를 먹고 방문 처리를 해주었었다. 상어가 물고기를 여러마리 먹으면 상어의 크기가 커져 예전에는 자신의 몸집과 같거나 커 먹지 못했던 물고기들도 먹게 될 수 있기 때문에 상어와 크기가 같거나 큰 물고기들은 추후 방문을 위해 방문 처리를 하지 않고 지나가야 한다고 생각했다. 하지만, 이제 물고기를 하나만 먹고 bfs를 다시 돌게 변경했기 때문에, 해당 bfs 호출에서는 조건을 검증한 좌표는 모두 방문 처리를 해주었다.(좌표값이 0이거나 물고기 크기가 상어 크기와 같거나 작은 좌표)
6. 하지만, 여기서 문제. BFS를 언제까지 돌것이냐 ? 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청해야 하기 때문에 BFS를 더이상 돌면 안된다. 따라서 현재 좌표에서 먹을 수 있는 물고기까지의 최단거리를 나타내는 eat 튜플의 첫번째 값의 초기값을 최대로 설정해주었다.
7. 만약 BFS를 다 돌고 왔는데도 eat 튜플의 첫번째 값이 sys.maxsize라면 graph를 다 돌았는데도 더이상 먹을 수 있는 물고기가 없다는 뜻이므로 while문을 종료하게 해주었다.

사실 2와 3을 합쳐 graph[startY][startX]를 while True: 바로 밑에다 써주면 되지만, 2와 같은 위치에만 썼을 때 왜 안되는지 그 이유를 설명하고 싶어서 위와 같이 코드를 썼다.

 

2) 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹어야 한다. 

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

처음에는 상, 좌, 하, 우 순서로 탐색을 하다가 잡아먹을 수 있는 물고기를 발견하는 즉시 잡아먹는 방식으로 구현했다. 하지만 이는 가장 위에 있는 물고기, 다음 가장 왼쪽에 있는 물고기를 의미하지 않았다. 그 이유는 한 칸 이동할 때만 상, 좌, 하, 우 순서로 탐색을 하는 것이기 때문이다. 한 경로에서 탐색을 하다 물고기 크기가 상어보다 더 크거나 이미 방문한 곳이라면 상, 좌, 하, 우 순서로 좌표를 바꾸기 때문에 결론적으로 발견한 (먹을 수 있는) 물고기가 가장 위에 있는, 왼쪽에 있는 물고기를 의미하지 않는다.

따라서, 탐색 중 물고기를 발견하면 좌표를 저장해두었다가, 탐색 범위를 넓히기 직전 (y, x) 값이 가장 작은 물고기 좌표를 채택해서 잡아먹는 방식으로 다시 구현했다. 

eat = min(eat, (cnt + 1, nextY, nextX))

 

이렇게 하면 최단거리, 가장 위쪽 좌표, 가장 왼쪽 좌표 순으로 비교하여 min값을 저장하게 된다.

 

💡 풀이 코드 

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = []
visited = [[False] * n for _ in range(n)]
startX = 0
startY = 0
cntTotal = 0
sharkSize = 2
sharkCnt = 0

for i in range(n):
    l = list(map(int, sys.stdin.readline().split()))
    graph.append(l)

    for j in range(n):
        if l[j] == 9:
            startY = i
            startX = j

def bfs(graph, startY, startX):
    global cntTotal, sharkSize, sharkCnt
    visited = [[False] * n for _ in range(n)]

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

    queue = deque()
    queue.append((0, startY, startX))  # Change initial count to 0
    visited[startY][startX] = True
    eat = sys.maxsize, startY, startX

    while queue:
        cnt, y, x = queue.popleft()

        for i in range(4):
            nextX = x + dx[i]
            nextY = y + dy[i]

            if 0 <= nextX < n and 0 <= nextY < n:
                if graph[nextY][nextX] > sharkSize or visited[nextY][nextX]: continue
                if 0 < graph[nextY][nextX] < sharkSize:

                    eat = min(eat, (cnt + 1, nextY, nextX))

                visited[nextY][nextX] = True
                queue.append((cnt + 1, nextY, nextX))
    return eat

graph[startY][startX] = 0 # 이거 때메 자꾸 값 이상함 (맨처음 시작점-9도 graph 값 초기화 필요)
while True:
    count, startY, startX = bfs(graph, startY, startX)
    if count == sys.maxsize:
        break
    graph[startY][startX] = 0
    sharkCnt += 1
    cntTotal += count

    if sharkCnt == sharkSize:
        sharkSize += 1
        sharkCnt = 0

print(cntTotal)

 

먼저, 예제 입력 3을 가지고 bfs 동작 방식에 대해 설명해보겠다. 

 

이 문제는 현재 위치에서 조건 내의 모든 노드를 탐색하여 해당 조건에 부합하는지 확인해야 한다. 이 점에서 Bfs, Dfs 중 사용할 알고리즘을 먼저 선택해야 한다. 이 문제는 상어보다 크기가 작은 물고기가 존재할 때까지 계속 탐색해야 한다. 즉, 매번 물고기를 먹고 현재 위치에서 최단거리를 이동하여 먹을 수 있는 물고기를 찾아 이동해야 한다. 이러한 점에서 Bfs를 선택했다. (최단거리에 있는 물고기를 찾아야 하고, 이 문제에선 상어보다 크기가 작은 물고기에 도달하기 위해 모든 경로를 구할 필요가 없기 때문에 Dfs가 아니다.) 

하지만, 최단거리에 있는 물고기라고 바로 먹으면 안된다. 최단거리 상의 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹어야 한다. 즉, 최단거리 상의 물고기를 다 저장해놨다가 가장 위에 있는, 가장 왼쪽에 있는 물고기를 먹고 그곳에서 또 최단거리 상의 먹을 수 있는 물고리를 찾아 탐색해야 한다. 

결론적으로, 이 문제는 Bfs, Dfs 등의 그래프 이론을 잘 이해해야 풀 수 있는 문제이다. 문제에서 요구하는 바가 무엇인지 확실하게 이해하고 해답을 얻기 위해 어떠한 방식으로 Bfs, Dfs를 활용하여 을 돌릴지 생각을 곰곰히 해야 풀리는 문제이다.

 

느낀점 : 그냥 문제 빨리 풀어버리고 싶어서 BFS로 대충 구현한 후, 예제 입력으로 때려박으면서 출력 어떻게든 맞춰보려고 하니까 역시 틀렸다. 문제 원리부터 잘 이해하고 원리에 따라 잘 설계한 후 푸는게 진짜 중요한 거 같다. 즉, 문제에서 해답에 도달하기 위해 어떻게 그래프 탐색을 진행할지 생각해보고, 그래프 탐색 과정을 머릿속으로 먼저 그려본 후 코드를 짜면  좀 더 빨리 정답에 근접할 수 있을 것 같다. 

 

 

*참고

 

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

DFS, BFS의 설명, 차이점

https://great-park.tistory.com/26

[BOJ/백준] 16236번 아기 상어 (Python 파이썬)

https://zu-techlog.tistory.com/82

[BOJ] 백준 16236번 아기 상어 - 파이썬(Python)