BOJ - 어른 상어 19237번 (python)

❓ 문제 - 백준 어른 상어 19237번 - python 풀이법

 

출처 

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

19237번: 어른 상어

 

 

 

📝 문제해결법

1. 이 문제는 구현로 풀었다.

• sea(격자칸에 상어의 번호로 존재 표시), smell(격자칸에 존재하는 상어의 냄새표현 위해 냄새 타이머, 상어의 번호), s_dir(현재 상어의 방향), dir(상어의 번호와 상어의 현재방향에 따른 다음 방향 정보) 리스트를 활용하여 문제를 푼다.
• count로 초 수를 세고, 만약 이동이 1000초 이상되었다면 -1을 출력한다. while 문을 돌면서 s_smell() 함수로 현재 상어의 위치에 냄새를 뿌리고, move() 함수로 상어의 이동을 처리한다. 또한 상어 이동시, 퇴출되는 상어의 수를 카운트 하여, 만약 이동이 끝난 후 퇴출된 상어의 수가 (m-1)개, 즉 상어 1만 남아있으면 while문을 빠져나와 count(정답)을 출력한다.
• 만약 이동이 끝났는데도 격자판에 상어 1 이외에 다른 상어도 존재하면 뿌린냄새의 타이머를 -1 해준다.

2. move()

• 상어 이동이 한 초에 한번에 이루어지므로 이동에 s 리스트를 이용한다.
• 모든 격자판을 돌면서 상어가 존재한다면, 해당 위치의 상어의 번호와 그 상어의 방향 정보를 가져온다.
• 상어의 번호와 현재 방향 정보에 해당하는 우선순위로 4방향을 탐색하면서 먼저 4방향에 위치가 격자판 범위 내에서, 상어의 냄새가 존재하지 않을 때 이동할 위치에 만약 상어가 존재하지 않다면 해당 위치로 상어를 이동시켜준다. 만약 해당 위치에 상어가 존재한다면 상어의 숫자를 비교해서 숫자가 더 크다면 그 상어를 퇴출 시키고 퇴출 상어 수를 1 증가시킨다.
• 만약 4방향 다 탐색했는데 모두 상어의 냄새가 존재한다면, 다시 우선순위에 맞춰 4방향을 탐색하면서 상어의 냄새가 현재 상어 번호에 해당하는 냄새라면 그 곳으로 이동한다.
• 모든 이동 처리 후 원래 격자판 정보를 s(이동 후 격자판 정보)로 변경해준다.

3. 문제 풀면서 느낀점

• 이동이나 구현시에 고려해야할 요소가 많을 때 해당 정보를 저장할 리스트를 만들어서 처리해야겠다.
• 또한 한번에 이동이 일어나는 경우 이동을 위해 선언한 리스트와 과 이동 전 상태의 리스트를 분리시켜 처리해야한다.

 

💻 소스코드

import copy

n, m, k = map(int, input().split())
sea = [list(map(int, input().split())) for _ in range(n)]
smell = [[[0, 0] for _ in range(n)] for _ in range(n)]

s_dir = [0] + list(map(int, input().split()))

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

for i in range(m):
    array = []
    for j in range(4):
        array.append(list(map(int, input().split())))
    dir.append(array)

def move(sea):
    global out
    s = copy.deepcopy(sea)
    for i in range(n):
        for j in range(n):
            if sea[i][j] == 0:
                continue
            s_n = s[i][j]
            d = s_dir[s_n]
            x, y = i, j
            what = False
            for p in range(4):
                nd = dir[s_n][d-1][p]
                nx = x + dx[nd-1]
                ny = y + dy[nd-1]
                if not(0<=nx<n and 0<= ny<n):
                    continue
                if smell[nx][ny][1] == 0:
                    if s[nx][ny] == 0:
                        s[nx][ny] = sea[x][y]
                        s[x][y] = 0
                    else:
                        if s[nx][ny] > s[x][y]:
                            s[nx][ny] = sea[x][y]
                        out += 1
                        s[x][y] = 0
                    s_dir[s_n] = nd
                    what = True
                    break
            if what:
                continue

            for p in range(4):
                nd = dir[s_n][d-1][p]
                nx = x + dx[nd - 1]
                ny = y + dy[nd - 1]
                if not (0 <= nx < n and 0 <= ny < n):
                    continue
                if smell[nx][ny][1] == s_n:
                    s[nx][ny] = sea[x][y]
                    s[x][y] = 0
                    s_dir[s_n] = nd
                    break
    return s

def s_smell(k):
    for i in range(n):
        for j in range(n):
            if sea[i][j] != 0:
                smell[i][j][0], smell[i][j][1] = k, sea[i][j]

def smell_down():
    for i in range(n):
        for j in range(n):
            if smell[i][j][1] == 0:
                continue
            if smell[i][j][0] == 1:
                smell[i][j][0], smell[i][j][1] = 0, 0
            else:
                smell[i][j][0] -= 1

count = 0
out = 0
while True:
    if count >= 1000:
        count = -1
        break
    s_smell(k)
    sea = copy.deepcopy(move(sea))
    count += 1
    if out == m-1:
        break
    smell_down()

print(count)