[백준 19237] 어른 상어 - Python

Algorithm

구현, 시뮬레이션

Logic

풀이 순서

1. 상어가 처음 위치한 좌표로 sharkInfo와 sharkScent를 초기화한다.
2. 시간을 늘려가면서 다음을 수행한다.
   1. sharkInfo에 들어있는 상어들을 하나씩 이동시킨다.
      • 이동 rule
        1. 아무 냄새 없는 칸 찾기 -> 그런 칸이 여러개라면 우선순위를 따른다.
        2. 자신의 냄새가 있는 칸 찾기 -> 그런 칸이 여러개라면 우선순위를 따른다.
   2. 같은 위치에 여러 상어가 위치한다면, 가장 작은 번호의 상어를 제외하고 모두 없애준다.
   3. 현재 scentMap에 냄새가 남아있다면, 이 냄새가 남아있을 시간을 -1한다. (시간이 흐름을 의미)
   4. sharkInfo를 보면서 상어가 옮겨간 위치에 sharkScent를 업데이트한다.
3. 시간이 1000초를 초과하면 -1을 출력한다.

Review

걸린 시간: 몇날 몇일 ... 붙잡고 있었음

---

맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다.

---

라고 문제에 명시돼있는데.. 계속 상어를 먼저 움직인 다음 원래 자리에 냄새를 남기는 방식으로 구현했다.

왜 그랬을까 내가 ..

이렇게 sequence가 확실히 정해져있는 문제는 순서를 절대 절대 절대 헷갈리면 안된다... 삼성 문제 대부분이 이런 식이구.. 문제 풀기 전에 구현해야할 순서를 먼저 넘버링한 후에 구현해야겠다 ㅠㅠ

많은 것을 배운 문제였다.

 

Code

N, M, K = map(int, input().split())
sharkMap = [[int(x) for x in input().split()] for _ in range(N)]
sharkDir = [int(x) - 1 for x in input().split()]
sharkPriority = [[[int(x) - 1 for x in input().split()] for _ in range(4)] for _ in range(M)]
sharkScent = [[[] for _ in range(N)] for _ in range(N)]
sharkInfo = []
pos = [[-1, 0], [1, 0], [0, -1], [0, 1]]    # 위, 아래, 왼쪽, 오른쪽 순으로 봄


def isIn(y, x):
    if 0 <= y < N and 0 <= x < N:
        return True
    return False


def spreadScent(ny, nx, num):
    sharkScent[ny][nx] = [num, K]  # 향기 map에는 상어 번호와 향기 지속시간이 필요함


def timePass():
    for i in range(N):
        for j in range(N):
            if len(sharkScent[i][j]) > 0:
                sharkScent[i][j][1] -= 1
                if sharkScent[i][j][1] == 0:
                    sharkScent[i][j].clear()


def moveShark(y, x, num, Dir):
    global newShark
    sharkPos = sharkPriority[num][Dir]
    # 빈칸 우선순위 찾기
    for i in range(4):
        ny = y + pos[sharkPos[i]][0]
        nx = x + pos[sharkPos[i]][1]
        if isIn(ny, nx) and len(sharkScent[ny][nx]) == 0:
            newShark.append([ny, nx, num, sharkPos[i]])
            # spreadScent(y, x, num)
            return

    # 자기 냄새 우선순위 찾기
    for i in range(4):
        ny = y + pos[sharkPos[i]][0]
        nx = x + pos[sharkPos[i]][1]
        if isIn(ny, nx) and sharkScent[ny][nx][0] == num:
            newShark.append([ny, nx, num, sharkPos[i]])
            # spreadScent(y, x, num)
            return

def toMap(sharkInfo):
    arr = [[-1 for _ in range(N)] for _ in range(N)]
    for shark in sharkInfo:
        arr[shark[0]][shark[1]] = shark[2]
    return arr

for idx in range(M):
    for i in range(N):
        for j in range(N):
            if sharkMap[i][j] - 1 == idx:
                sharkInfo.append([i, j, idx, sharkDir[idx]])    # 상어 y, x, 번호, 방향
                spreadScent(i, j, idx)

# print(sharkInfo)
# print(sharkPriority)
time = 0
while time <= 1000:
    if len(sharkInfo) == 1:  # 1번 상어만 살아남음
        break

    # print("time: "+ str(time))
    # arr = toMap(sharkInfo)
    # for i in range(N):
    #     out = ""
    #     for j in range(N):
    #         out += str(arr[i][j]) + " "
    #     print(out)
    # print("\n")


    newShark = []
    while sharkInfo:
        shark = sharkInfo.pop()
        y = shark[0]
        x = shark[1]
        num = shark[2]
        Dir = shark[3]
        moveShark(y, x, num, Dir)
    # print(newShark)
    sharkInfo = newShark[:]
    sharkInfo = sorted(sharkInfo, key=lambda t: (t[0], t[1], t[2]))

    prev = sharkInfo[0]
    removeList = []
    for i in range(1, len(sharkInfo)):
        if prev[0] == sharkInfo[i][0] and prev[1] == sharkInfo[i][1]:  # 상어 같은 위치에 존재
            removeList.append(sharkInfo[i])
        prev = sharkInfo[i]

    for removeItem in removeList:
        rIdx = sharkInfo.index(removeItem)
        sharkInfo.pop(rIdx)

    timePass()

    for shark in sharkInfo:
        spreadScent(shark[0], shark[1], shark[2])

    time += 1
    # print(sharkInfo)

# print(time)
print(time if time <= 1000 else -1)