[백준] 19237번 어른 상어 - 파이썬(Python)

문제 (링크)

 

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

19237번: 어른 상어

 

나의 풀이

import sys
input = sys.stdin.readline
# 1번 상어는 모두 쫓아낼 수 있음
# N * N 그래프에 M 마리의 상어, k = 냄새 지속시간
n, m, k = map(int, input().split())
graph = []
sharks = [[] for _ in range(m + 1)]

# 위, 아래, 왼쪽, 오른쪽
moves = [
    [],
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1]
]

for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        if row[j] != 0:
            sharks[row[j]].append([i, j])
    
    graph.append(row)

current_d_list = list(map(int, input().split()))

for i in range(1, m + 1):
    sharks[i].append(current_d_list[i - 1])

sharks_preference = {}
for i in range(1, m + 1):
    sharks_preference[i] = [0]
    for j in range(1, 5):
        sharks_preference[i].append(list(map(int, input().split())))

"""
sharks[i][0]: i번째 상어의 현재 위치
sharks[i][1]: i번째 상어가 현재 바라보는 방향
"""

"""
sharks_preference[i][j]: i번째 상어가 j방향을 보고 있을 때 방향 우선순위 리스트
"""

# stage
# 1. 움직인다. (냄새 정보 확인) 
# 아무 냄새가 없는 칸으로 먼저 이동 / 자신의 냄새가 있는 칸으로 (가능한 칸이 여러개일 경우 우선순위를 따름)
# 2. 겹치는지 확인한다. (죽는 상어가 있는지 확인)
# 3. 냄새를 기록 및 업데이트한다.

graph_smell = [[[0, 0] for _ in range(n)] for _ in range(n)]
# 첫 냄새 기록
for i in range(1, m + 1):
    graph_smell[sharks[i][0][0]][sharks[i][0][1]][0], graph_smell[sharks[i][0][0]][sharks[i][0][1]][1] = i, k


# 내 냄새가 있는 방향 확인
def my_smell_check(graph_smell, shark_num):
    current_shark_loc = sharks[shark_num][0]
    current_shark_d = sharks[shark_num][1]
    preferences = sharks_preference[shark_num][current_shark_d]

    for direction in preferences:
        x, y = current_shark_loc[0] + moves[direction][0], current_shark_loc[1] + moves[direction][1]

        if 0 <= x < n and 0 <= y < n:
            if graph_smell[x][y][0] == shark_num:

                return [x, y, direction]

# 비어있는 공간 확인
def empty_check(graph_smell, shark_num):
    current_shark_loc = sharks[shark_num][0]
    current_shark_d = sharks[shark_num][1]
    preferences = sharks_preference[shark_num][current_shark_d]

    for preference in preferences:
        x, y = current_shark_loc[0] + moves[preference][0], current_shark_loc[1] + moves[preference][1]

        if 0 <= x < n and 0 <= y < n:
            if graph_smell[x][y][0] == 0:
                return [x, y, preference]
    
    # 빈 곳이 없으면 False 리턴
    return False
    
# 죽는 상어가 있는지 확인
def check_shark_dead():
    dead_num = 0
    for i in range(1, m):
        if sharks[i][0] == -1:
            continue

        for j in range(i + 1, m + 1):
            if sharks[j][0] == -1:
                continue
            
            i_shark_loc = sharks[i][0]
            j_shark_loc = sharks[j][0]

            if i_shark_loc == j_shark_loc:
                dead = max(i, j)
                sharks[dead][0] = -1
                dead_num += 1
    
    return dead_num

# 살아있는 상어의 수
remain_shark = m
# 이동 횟수
ans = 0
# 현재 상어위치 기록 (냄새 기록을 위한 위치)
current_loc_shark = [[0, 0]] * (m + 1)

while remain_shark > 1 and ans < 1001:
    # 상어 움직임
    for i in range(1, m + 1):
        # 현재 상어가 죽어있다면 건너뜀
        if sharks[i][0] == -1:
            continue

        current_loc = sharks[i][0]
        current_loc_shark[i] = current_loc
        empty_move = empty_check(graph_smell, i)

        # 비어있는 곳부터 탐색
        if empty_move:
            # 비어있는 곳 중 이동할 곳이 있다면 해당 위치로 이동 후 sharks 리스트 업데이트
            new_loc_x, new_loc_y, new_d = empty_move[0], empty_move[1], empty_move[2]
            sharks[i][0][0], sharks[i][0][1] = new_loc_x, new_loc_y
            sharks[i][1] = new_d
        
        else:
            # 비어있는 곳 없을 때 자신의 냄새 있는 곳 탐색, 이동 후 sharks 리스트 업데이트
            smell_move = my_smell_check(graph_smell, i)
            new_loc_x, new_loc_y, new_d = smell_move[0], smell_move[1], smell_move[2]
            sharks[i][0][0], sharks[i][0][1] = new_loc_x, new_loc_y
            sharks[i][1] = new_d

    # 죽은 상어 있는지 확인 후 업데이트
    dead_num = check_shark_dead()
    remain_shark -= dead_num

    # 기존 존재하던 냄새 업데이트 (1 빼줌)
    for i in range(n):
        for j in range(n):
            if graph_smell[i][j][0] != 0:
                graph_smell[i][j][1] -= 1
            
            if graph_smell[i][j][1] == 0:
                graph_smell[i][j][0] = 0

    # 살아있는 상어에 대하여 새로운 냄새 생성
    for i in range(1, m + 1):
        if sharks[i][0] != -1:
            x, y = current_loc_shark[i][0], current_loc_shark[i][1]
            graph_smell[x][y] = [i, k]
    
    ans += 1

if ans > 1000:
    print(-1)
else:
    print(ans)

 

풀이법 및 코드 설명

난이도가 꽤 있는 구현 문제라서 시간이 정말 오래걸렸다.

 

오프라인 스터디 2시간 동안 풀다가 결국 실패하였고, 기존 코드의 문제점을 파악한 후 다음 날 재도전 해 30~40분 더 걸려서 풀 수 있었다.

 

입력값이 너무 길고 복잡해서 이걸 정리하는데도 조금 벅찼지만, 이 부분이 완성되니 움직임이나 냄새 기록 등의 구현에선 나름 편하게 할 수 있었다.

 

개인적으로 복잡한 구현 문제의 키포인트는 각 동작들을 함수화하여 잘 나누는 것이라 생각한다.

 

이것이 되지 않으면 오류 확인과 수정이 사실상 불가능하고 길을 잃을 가능성이 높기 때문이다.

 

이번 문제 역시 다음으로 움직일 방향을 정하는 동작과 이동 후 죽는 상어가 있는지 확인하는 동작을 각각 함수화하였다.

 

이후, 주석으로 적은 순서대로 동작을 실행시켜줬다.

 

1. 살아있는 상어에 대하여, 자신 주위 방향 중 빈 곳을 먼저 탐색하고, 빈 곳이 있다면 우선순위에 따라 움직인다.

 

2. 빈 곳이 없다면 자신의 냄새가 있는 곳을 탐색하고, 그러한 곳이 있다면 우선순위에 따라 움직인다.

(움직이지 못하는 경우는 없다는 조건이 있으므로, 1번 단계에서 움직이지 못한 상어는 2번 단계에서 무조건 움직일 것이므로, 예외처리는 따로 고려하지 않는다.)

 

3. 1, 2 단계를 거친 후, 상어의 위치를 파악하여 위치가 겹치는 상어가 있는지 확인하고, 만약 위치가 겹친다면 번호가 높은 상어를 쫓겨났다는 상태로 업데이트 해준다.

 

4. 쫓겨난 상어의 수를 현재 남아있는 상어의 수에서 빼준다.

 

5. 살아있는 상어에 대하여, 그들이 이동하기 직전 위치에 새 냄새를 기록해준다.