문제링크

19237 - 어른상어

문제설명

1번부터 M번 사이의 번호가 붙은 상어 M마리가 N*N크가의 격자 상에 있다. 초기는 모든 상어가 자기 위치에 냄새를 뿌린다.
1초마다의 이동

• 모든 상어는 상하좌우 인접칸으로 이동하고 냄새를 뿌린다.
• 상어가 K번 이동하면 (k초뒤) 냄새는 사라진다.
• 이동 후 한칸에 여러 상어가 있으면 가장 번호가 작은 상어만 살아남는다 (1번이 제일 쎔)

이동 방향은 1 위, 2 아래, 3 왼쪽, 4 오른쪽으로 정의한다. 인접칸으로 이동하는 방향은

1. 인접한 네 칸중 아무 냄새도 없는 칸
2. 1번에 만족하는 칸이 없으면 내 냄새가 있는 칸

으로 이동한다. 만약 만족되는 칸이 여러개면, 입력으로 주어진 바라보는 방향 마다의 특정 우선 순위를 따른다.

상어의 머리 방향은 초기는 입력과 같이, 그 이후는 이동 방향이 보는 방향이다.
각 상어의 위치, 바라보는 방향, 그리고 상어마다의 이동 우선순위가 다음과 같이 입력으로 주어진다.

5 4 4 // N M k
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0 // 격자위 상어들의 위치
4 4 3 1 // 상어들의 초기 바라보는 방향
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2 // 상어 1의 상-하-좌-우 바라볼때의 이동 우선순위 
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3 // 상어 2의 상-하-좌-우 바라볼때의 이동 우선순위 
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4 // 상어 3의 상-하-좌-우 바라볼때의 이동 우선순위 
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3 // 상어 4의 상-하-좌-우 바라볼때의 이동 우선순위 

이때 1번 상어만 남는데 걸리는 시간은?

문제 풀이

입력이 엄~~~청나게 길고 많아서 디버깅하기 어려울 것 같아 보였다,, 그래서 한방에 풀려고 수도코드를 최대한 자세히 써서 코드로 옮겼다.

입력받기

상어의 위치와 냄새는
smell[i][j] : (i,j)칸 위의 [상어번호, 냄새의 남은시간]
shark[i][j] : (i,j)칸 위에 있는 상어 번호 저장 -> 한칸에 여러 상어 있는지 검사용
shark[k] : k번 상어가 d 방향 보고 (x,y)에 위치함을 [d, (x,y)]와 같이 저장하는 딕셔너리
와 같이 크게 세개의 리스트와 딕셔너리를 선언해서 저장했다.

각 상어마다 바라보는 방향에 따른 우선순위는 다음과 같이 저장했다.
priority[k][d] : k번 상어가 방향 d를 바라볼때의 우선순위

smell = [[0 for _ in range(N)] for _ in range(N)] # smell[i][j] = [상어번호, 남은시간]
shark = [[[] for _ in range(N)] for _ in range(N)] # shark[i][j] = [k] : (i,j)에 현재 k번 상어있음 -> 한칸에 여러 상어 있는지 검사용
sharks = {} # shark[k] = [d, (x,y)] : k번 상어가 d 방향 보고 (x,y)에 위치
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0:
            shark[i][j].append(tmp[j])
            sharks[tmp[j]] = [(i,j)]
            smell[i][j] = [tmp[j], K] #초기 냄새, 시간 퍼뜨리기

direction = list(map(int, input().split()))
for i in range(M):
    sharks[i+1].append(direction[i])

priority = defaultdict(list) # priority[k][d] : k번 상어의 방향 d 우선순위
for i in range(M):
    for j in range(4):
        # i번 상어의 각 네방향 마다의 우선순위
        priority[i+1].append(list(map(int, input().split())))

매 초마다의 이동

초마다의 이동은

1. 우선 순위에 따라 인접 칸으로 상어 이동

    for s in sharks.keys():
        (x, y), d = sharks[s]
        count_empty = [] # 빈칸 count
        count_me = [] # 내 냄새가 있는 칸
        # 4방향 검사하기
        for i in range(1, 5):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny):
                # 빈칸 count
                if smell[nx][ny] == 0:
                    count_empty.append(i)
                # 내 냄새가 있는 칸인지 count
                elif smell[nx][ny][0] == s:
                    count_me.append(i)
        
        if len(count_empty) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_empty[0]]][y+dy[count_empty[0]]].append(s)
            sharks[s] = [(x+dx[count_empty[0]],y+dy[count_empty[0]]), count_empty[0]]
        elif len(count_empty) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_empty:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break

        elif len(count_me) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_me[0]]][y+dy[count_me[0]]].append(s)
            sharks[s] = [(x+dx[count_me[0]],y+dy[count_me[0]]), count_me[0]]
        elif len(count_me) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_me:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break

겹치는 코드가 많아서 너무 길어진거같다... 겹치는 부분 따로 함수로 뺴면 더 깔끔할듯

2. 한칸에 여러 상어 있는지 검사하고 내쫓기
   : 2마리 이상 있는 칸에 대해서 오름차순으로 정렬하고, 제일 번호가 작은 상어 빼고 전부 내보낸다.

    for i in range(N):
        for j in range(N):
            if len(shark[i][j]) > 1:
                shark[i][j].sort()
                # 제일 번호 작은 상어 빼고 다 내보내기
                del_shark = shark[i][j][1:]
                for s in del_shark:
                    (x, y), d = sharks[s]
                    shark[x][y].remove(s)
                    del(sharks[s])
                    n_shark -= 1

3. 각 칸의 냄새에 대해 남은 시간 -= 1

    for i in range(N):
        for j in range(N):
            if smell[i][j] != 0:
                if smell[i][j][1] == 1:
                    smell[i][j] = 0
                else:
                    smell[i][j][1] -= 1

4. 이동한 칸에 대해서 냄새 뿌리기

    for s in sharks.keys():
        (x, y), d = sharks[s]
        smell[x][y] = [s, K]

의 순서로 구현한다.

전체 코드

전체 코드는 다음과 같다.

import sys
from collections import deque, defaultdict

input = sys.stdin.readline

dx = [0, -1, 1, 0, 0] # 상1하2좌3우4
dy = [0, 0, 0, -1, 1]

N, M, K = map(int, input().split())
n_shark = M
def in_range(x, y):
    if x in range(N) and y in range(N):
        return True
    return False

smell = [[0 for _ in range(N)] for _ in range(N)] # smell[i][j] = [상어번호, 남은시간]
shark = [[[] for _ in range(N)] for _ in range(N)] # shark[i][j] = [k] : (i,j)에 현재 k번 상어있음 -> 한칸에 여러 상어 있는지 검사용
sharks = {} # shark[k] = [d, (x,y)] : k번 상어가 d 방향 보고 (x,y)에 위치
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0:
            shark[i][j].append(tmp[j])
            sharks[tmp[j]] = [(i,j)]
            smell[i][j] = [tmp[j], K] #초기 냄새, 시간 퍼뜨리기

direction = list(map(int, input().split()))
for i in range(M):
    sharks[i+1].append(direction[i])

priority = defaultdict(list) # priority[k][d] : k번 상어의 방향 d 우선순위
for i in range(M):
    for j in range(4):
        # i번 상어의 각 네방향 마다의 우선순위
        priority[i+1].append(list(map(int, input().split())))

time = 0
# 매초마다의 동작
while True:
    if n_shark == 1:
        print(time)
        break
    if time >= 1000:
        print(-1)
        break
    
    # 모든 상어 이동
    for s in sharks.keys():
        (x, y), d = sharks[s]
        count_empty = [] # 빈칸 count
        count_me = [] # 내 냄새가 있는 칸
        # 4방향 검사하기
        for i in range(1, 5):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny):
                # 빈칸 count
                if smell[nx][ny] == 0:
                    count_empty.append(i)
                # 내 냄새가 있는 칸인지 count
                elif smell[nx][ny][0] == s:
                    count_me.append(i)
        
        if len(count_empty) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_empty[0]]][y+dy[count_empty[0]]].append(s)
            sharks[s] = [(x+dx[count_empty[0]],y+dy[count_empty[0]]), count_empty[0]]
        elif len(count_empty) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_empty:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break

        elif len(count_me) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_me[0]]][y+dy[count_me[0]]].append(s)
            sharks[s] = [(x+dx[count_me[0]],y+dy[count_me[0]]), count_me[0]]
        elif len(count_me) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_me:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break
    
    # 한칸에 여러 상어 있는지?
    for i in range(N):
        for j in range(N):
            if len(shark[i][j]) > 1:
                shark[i][j].sort()
                # 제일 번호 작은 상어 빼고 다 내보내기
                del_shark = shark[i][j][1:]
                for s in del_shark:
                    (x, y), d = sharks[s]
                    shark[x][y].remove(s)
                    del(sharks[s])
                    n_shark -= 1

    # 남은시간 -= 1
    for i in range(N):
        for j in range(N):
            if smell[i][j] != 0:
                if smell[i][j][1] == 1:
                    smell[i][j] = 0
                else:
                    smell[i][j][1] -= 1

    # 냄새 뿌리기
    for s in sharks.keys():
        (x, y), d = sharks[s]
        smell[x][y] = [s, K]
    
    time += 1

처음에 잘못 생각했던 부분이
1. 시간이 1000초이고 격자에 상어 1마리만 있을때
-> 이때는 1000이 정답이다.
2. 포문 돌면서 list 삭제,,,, 이건 매번 헷갈리느듯 ^_ㅠ

입력이 너무 길고 시뮬레이션 과정이 복잡해서 처음에 틀렸습니다 나와서 막막했는디.. 틀린 부분 빨리 찾아서 고쳤다 ^_^

소요시간

2시간 !