[BOJ][Python]16236번 풀이

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

16236번: 아기 상어

from collections import deque
import sys
ssr = sys.stdin.readline

def bfs():#n^2 - 1 돌면서 현재 상태에서 먹을 수 있는 물고기를 전부 추가
    visited = [[0 for _ in range(n)] for _ in range(n)]
    while q:
        tmp = q.popleft()
        visited[tmp[0]][tmp[1]] = 1
        for i in dp:
            if 0 <= tmp[0] + i[0] < n and 0 <= tmp[1] + i[1] < n:#테이블 범위를 벗어나지 않을 때
                if t[tmp[0] + i[0]][tmp[1] + i[1]] <= size and visited[tmp[0] + i[0]][tmp[1] + i[1]] == 0:#이동이 가능할 때
                    visited[tmp[0] + i[0]][tmp[1] + i[1]] = 1#이동했다
                    if 0 < t[tmp[0] + i[0]][tmp[1] + i[1]] < size:#먹을 수 있을 때
                        fish_list.append((tmp[0] + i[0], tmp[1] + i[1], tmp[2]+1))#물고기 리스트에 추가
                    else:#못먹거나 0일 때
                        q.append((tmp[0] + i[0], tmp[1] + i[1], tmp[2] + 1))#이동했다고치고 bfs를 위해 추가
    
def eat_fish():
    global size, eat, fish, ans
    if len(fish_list) == 0:
        fish = 0#fish_list가 비었다는 건 먹을 수 있다는게 없다는 뜻, 반복문을 끝내기 위해 0으로
        return
    fish_list.sort(key = lambda x:(x[2],x[0],x[1]))
    tmp = fish_list.pop(0)
    q.append(tmp)
    eat += 1
    fish -= 1
    ans = tmp[2]
    if size == eat:
        size += 1
        eat = 0
    t[tmp[0]][tmp[1]] = 0
        
n = int(ssr())
t = [list(map(int, ssr().split())) for _ in range(n)]
q = deque([])
fish = 0
for i in range(n):
    for j in range(n):
        if t[i][j] == 9:
            q.append((i,j,0))
            t[i][j] = 0
        elif t[i][j] > 0:
            fish += 1
dp = [(-1, 0), (0, -1), (0, 1), (1, 0)]
size = 2
eat = 0
ans = 0
while fish > 0:
    fish_list = []
    bfs()
    eat_fish()
print(ans)

대략 이틀간 문제 풀이 포스팅을 올리지 못했습니다. 이유는 이 문제를 풀고 있었기 때문인데요. 사실 제가 무언가를 혼자 힘으로 해결하기 위해서 끙끙대는 것은 크게 드문 일이 아닙니다. 뭔가 하나를 해결하기 위해 일주일이고 한 달이고 붙잡고 있을 때도 있으니까요. 그럴 때 인간은 스스로 성장하는 법을 깨우친다고 믿고 있습니다.

 

누군가는 그런 무식한 짓을 왜 하냐고 물을 수도 있겠습니다. 다른 이의 도움을 받으면 그 시간을 세이브하면서도 성장할 수 있다고 말하죠. 충분히 동의하는 말입니다. 실제로 저도 그런 경험을 했었고 방법을 배우고 다시 그걸 복기하면서 혼자 해보는 쪽이 시간적으로 훨씬 이득일 때가 많았구요.

 

다만 저는 다른 사람에게 도움을 요청하기 전에 단순하지만 까다로운 조건을 적용합니다. '더 이상 아무 방법도 떠오르지 않을 때' 저는 도움을 요청합니다. 반대로 말하자면 아주 조금이라도 시도할 방법이 생각나는 동안은 혼자서 하겠다고 고집을 부린다는 것이죠. 제가 이런 조건을 정해놓은 이유는 단순히 제가 욕심쟁이라서입니다. 저는 인간이 스스로 고민할 때 정신적으로 성장하는 부분까지 놓치고 싶지 않습니다. 까짓 지식 정도는 시간만 들이면 언제든지 얻을 수 있죠. 하지만 언제까지고 누군가에게 기대고 도움을 받는다면 정말 결정적인 순간에, 아무도 나를 도와주지 않을 때 크게 꺾인다는 것이 저의 지론입니다.

 

제가 정말 사랑하고 매일같이 가슴에 새기는 말 중에 니체의 '나를 죽이지 못하는 고통은 나를 더 강하게 만든다' 라는 말이 있습니다. 겪는 수라장의 수만큼 성장한다는 말과 같습니다. 너무 중2 같다고 생각하실지도 모르겠지만, 까짓 거 제 인생인데 조금 중2 같다면 또 어떤가요. 물론 폭풍에 꺾이지 않는 것은 단단한 나무가 아닌 갈대일지도 모릅니다. 세상의 풍파를 견뎌내는 데에는 유연함이 꽤 중요한 덕목이니까요. 저는 외골수 같은 기질이 있지만 그렇다고 장님은 아니거든요. 융통성이 있는 사람들의 능력을 인정하고 본받으려 합니다.

 

하지만 가끔 이렇게 고집을 부려야 한다고 판단하면 타협을 하지 않는 편이네요. 저는 이런 고난을 '허물 벗기'와 같다고 생각을 하곤 합니다. 파충류나 갑각류들은 허물을 벗으면서 더 커지고 더 단단해지죠. 하지만 자연계에는 허물을 벗는 과정 중에 허물을 제대로 벗지 못하고 죽는 생물들이 생각보다 많다고 합니다. 사람이 살면서 만나는 고난도 허물과 비슷하다고 생각합니다. 허물을 벗어내면 성장하고, 벗지 못하면 죽는 것이죠. 물론 말 그대로의 의미로 죽는다는 것은 아니고 성장을 포기한다 정도의 의미가 되겠네요. 그런 과정에서 누군가가 허물을 대신 벗겨준다면 살아날 것입니다. 그리고 다음에 올 허물 벗기를 대비해서 힘을 기른다면 다음번에는 죽지 않고 살아날 수도 있겠죠. 그래서 저는 딱히 무조건 혼자 힘으로 해야 한다고 누군가에게 강요할 생각은 없습니다. 죽느냐 사느냐가 달렸는데 혼자든 아니든 그게 뭐가 중요하겠습니까. 다만 저는 누군가가 도와주지 않을 미래를 대비해서 혼자 벗는 법을 연습하는 것에 초점을 두고 살아가고 있다 정도로 이해하시면 될 것 같습니다.

 

사설이 너무 길었습니다. 클래스 3++의 마지막 문제이기도 하고 저 스스로 이건 넘을 수 있는 벽이다 생각이 들었지만 며칠을 고민하다 보니 머릿속에 이런 말들을 되새기지 않았다면 꺾였을지도 모른다는 생각에 마음이 약해질 때를 대비해서 이런 글을 적는 것일 수도, 혹은 이 글을 다 읽어주실 다른 분들에게 이만큼 고뇌했습니다 하고 어필하는 것일지도 모르겠네요. 겨우 골드 3 가지고 뭐 이렇게 장황하게 써놨어라고 하신다면 드릴 말씀은 없겠지만 사람들마다 어렵게 여기는 것에는 개인차가 있으니까요. 확실한 건 제가 말이 많다는 것이겠네요. 

 

정말 말이 길었습니다. 문제 풀이로 빨리 넘어가죠. 일단은 bfs입니다. 다만 이때까지 풀었던 bfs와 다른 점은 갔던 곳을 또 갈 수 있다는 점입니다. 엥? 그럼 방문처리를 하지 말라는 뜻인가요? 물론 그건 아닙니다. 숱한 bfs 문제를 푸시면서 방문 처리를 안했다간 메모리 및 시간 초과가 난다는 점은 다들 알고 계실 겁니다. 그렇다면 어떻게 방문처리를 해야 해당 문제를 풀 수 있을지를 생각해봐야겠죠. 사실 이 부분에서 저는 고민을 많이 했습니다. 방문할 때마다 0에서 1씩 빼면서 최대한 갔던 곳을 안가도록 우선도를 선정해야 하나? 아니면 정말 방문처리를 하지 않고 모든 물고기의 위치를 저장한 리스트를 만들어서 그걸 거리 순, 위에 있는 순, 왼쪽에 있는 순으로 정렬을 하고 모두 더하면 되나? 등등의 고민을 하다가 어차피 bfs는 인접한 곳을 탐색하는 알고리즘이니까 인접한 곳에 물고기가 있다면 그 자체가 최적의 해가 아닌가? 못 먹는 경우는 어차피 조건문으로 거를 수 있으니까 그냥 모든 경우에 대해서 탐색을 진행하고 그중에서 가장 조건에 맞는 물고기를 먹으면 되는 것 아닐까? 라는 생각이 들었을 때부터 속도가 붙기 시작했습니다. 그래프 탐색이 생각보다 브루트 포스와 비슷한 성질을 가지고 있다는 부분을 망각했던 것 같아요.

 

그 뒤부터는 문제를 크게 크게 나눠보기 시작했습니다. 일단 처음에 상어 위치는 찾아야 하니까 9가 어디 있는지 찾으면서 이왕 반복문 도는 거 아까워서 물고기 숫자도 세어줬습니다. 나중에 물고기를 다 먹어치웠는지 비교할 때 상수로 쓸만할 것 같더라구요. 그다음엔 탐색을 해야겠죠. dfs는 사실 최소해를 구하는 데에는 그다지 강점이 있지 않아서 bfs로 진행했습니다. 생각보다 n의 범위가 크지 않습니다. 20이 최대 범위이니 총 원소의 갯수는 400개이고 모든 n^2-1개의 원소가 다 1이라도 모든 좌표에 대해서 bfs를 돌면서 먹을 수 있는 물고기를 찾는다고 하더라도 약 160000 정도밖에 안되더라구요. 그렇다면 그냥 400개 탐색하고 거기서 조건에 맞는 물고기를 찾도록 정렬을 해도 아무 상관이 없다고 생각했습니다(python sort의 시간 복잡도는 O(log(n))). 거기다 물고기를 먹을수록 조건에 맞는 물고기의 숫자가 줄어드니 사실 훨씬 짧은 시간 복잡도를 갖는 셈이죠. 그래서 bfs를 이때까지 해왔던 것처럼 방문처리를 해가면서 n^2-1개의 원소를 쭉 탐색합니다. 그리고 조건에 맞는 물고기가 나오면 fish_list에 넣어줍니다(deque를 만들어서 popleft 쓰려고 했는데 sort가 안먹어서 리스트로 했습니다 pop(0)가 O(n) 짜리긴 하지만 그래 봤자 최대 399번이라 괜찮아요). 먹을 수는 없지만 이동이 가능한 경우는 q에만 넣어서 탐색용으로 씁니다.

 

그리고 eat fish로 넘어와서 처음에는 걸린 시간순으로 먼저 정렬을 합니다(key = lambda를 이용해서 원하는 대로 정렬을 시킬 수 있습니다. 아주 좋으니까 꼭 익혀두시면 좋습니다). 그리고 위에 있는 순, 왼쪽에 있는 순으로 정렬해줍니다.(참고로 fish_list에 들어있는 원소는 튜플로 (행 번호, 열 번호, 도착하는데 걸린 시간)의 형태를 가졌습니다). 그렇게 하고 맨 왼쪽에 있는 원소를 뽑아주면 가장 가깝고, 가장 위에 있고, 가장 왼쪽에 있는 원소를 추출할 수 있는 것입니다. 그다음부터는 쉽죠. 먹은 물고기 수를 증가시키고 남은 물고기 수를 감소시키고 먹은 수와 상어 크기가 같다면 크기를 키우고 먹은 수를 0으로 바꿔주면 됩니다. 다만 여기서 놓치면 안되는 부분은 먹은 다음에는 꼭 값을 0으로 바꿔주셔야 되는 부분입니다. 바꾸지 않으면 계속 먹을 수 있는 물고기 리스트에 넣어버리기 때문에 원하는 결과가 나오지 않아요. ans에 이동 시간을 넣은 이유는 메인 반복문이 남은 물고기 수가 0이 되면 반복이 종료되기 때문입니다(처음부터 0마리이면 아예 반복문을 돌지 않고 초기화된 값인 0을 출력).

 

사실 다 풀고 보면 데이터가 작으니까 소위 말하는 무식한 코드를 짜도 풀 수 있는 문제가 되어버리다 보니 풀이가 그렇게 어렵지는 않은데요. 그래서 그런가 엄청 거창하게 고난이 어쩌구 허물이 어쩌구 했는데 문제 풀이가 잡소리보다 짧은 상황이 일어났습니다... 뭐 클래스 3 정복을 기념하면서 폭주 한 번 했구나 생각해주시면 감사하겠습니다. 지나고 보니 별 것 아니었다 라는 일은 늘 있는 일이니까요.