문제

BOJ 19237: 어른 상어 https://www.acmicpc.net/problem/19237

풀이

조건

• 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다.

• N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다.

• 상어가 뿌리는 냄새 조건

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

• 상어가 이동하는 조건

  1. 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다.
  2. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다.
  3. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다.
     • 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다.

• 상어 제거 조건

  • 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
  • 같은 영역에 상어가 겹치면 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

• 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

• 각 상어의 방향이 차례대로 주어지는데 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

• 맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

• 종료 조건

  • 1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다.
  • 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

풀이 순서

• 정보를 저장하는 방법

  • 상어 냄새 기록(board)
    

    • 각 위치에 [상어 번호, 기록된 시각] 으로 냄새를 저장한다.

  • 상어 위치 기록(check)
    

    • 2차원 배열로 상어 위치를 기록한다.

  • 상어 좌표 기록(shark_now_pos)
    

    • 상어 번호를 인덱스로 하는 배열에 상어 좌표를 저장한다.
    • 상어 이동시킬 때 순서대로, 빠르게 하기 위해

  • 상어 방향 기록(shark_now_dir)
    

    • 상어 번호를 인덱스로 하는 배열에 상어의 현재 방향을 저장한다.

  • 상어별 이동 우선순위 기록(shark_priority_info)
    

    • 상어의 번호가 인덱스가 된다.
    • 0번 상어는 없으므로 0 기록
    • 0번 방향은 없으므로 0 위치는 0 기록

• while문을 사용해 시뮬레이션을 진행한다.
  • 1000초 까지만 반복
• 모든 상어를 이동시킨다.
  • 1번부터 M번까지 상어를 차례로 이동시킨다.
  • 상어의 방향, 방향 우선순위 등을 확인하고 가능한 위치로 이동시킨다.
    • 아무 냄새 없는 칸이 있으면 해당 위치로 이동
    • 주위에 아무 냄새 없는 칸이 없으면 자신의 냄새가 있는 칸으로 이동
    • 이 때 상어가 겹치는건 신경쓰지말고 다른 배열에 기록해둔다.(n_board)
  • 겹쳐진 상어를 처리 하고 살아남은 상어 냄새, 위치를 기록한다.
• 오래된 냄새를 제거한다.
• 시뮬레이션이 종료될 수 있는지 확인한다.
  • 1번 상어만 남았는지 확인
• 시간 +1(time + 1)

코드

Python

import sys

# 공백, 위, 아래, 왼쪽, 오른쪽
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

N, M, K = map(int, sys.stdin.readline().rstrip().split())
board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

shark_now_pos = [[]] * (M + 1)  # 상어 번호 별로 위치한 좌표 저장할 배열
check = [[0 for _ in range(N)] for _ in range(N)]  # 상어가 존재하는 위치 저장할 배열
for i in range(N):
    for j in range(N):
        if board[i][j] != 0:
        	# 상어 번호 별로 위치한 좌표 저장
            shark_now_pos[board[i][j]] = [i, j]
            # 상어가 존재하는 위치 저장
            check[i][j] = board[i][j]
            # 냄새 저장
            board[i][j] = [board[i][j], 0]

# 상어 번호 별로 바라보는 방향 저장
shark_now_dir = list(map(int, sys.stdin.readline().rstrip().split()))
shark_now_dir.insert(0, 0)  # 0번 상어는 없어서 0 넣어줌

# 상어 번호, 방향 별로 방향 우선순위 저장
shark_priority_info = [[0 for _ in range(5)] for _ in range(M + 1)]
for i in range(1, M + 1):
    temp = []
    for j in range(1, 5):
        temp = list(map(int, sys.stdin.readline().rstrip().split()))
        shark_priority_info[i][j] = temp
        

# 상어가 이동할 수 있는 위치 확인하는 함수
def check_shark_move_pos(shark_num, shark_pos, direction, dir_priority):
    global n_board
    x = shark_pos[0]
    y = shark_pos[1]

	# 원래 있었던 위치는 0으로 바꿈
    check[x][y] = 0
    # 자신의 냄새가 있는 칸 나오면 기록할 배열
    now_shark_smell_pos = []
    
    # 아무 냄새 없는 칸이 있으면 거기로 이동
    for t in range(4):
        target_dir = dir_priority[t]  # 우선순위에 맞는 방향 가져옴
        nx = x + dx[target_dir]
        ny = y + dy[target_dir]
        # 격자 범위 체크
        if nx < 0 or ny < 0 or nx >= N or ny >= N:
            continue
		# 자기 냄새 있는 칸이면 기록
        if board[nx][ny] != 0 and len(board[nx][ny]) > 0 and board[nx][ny][0] == shark_num:
            now_shark_smell_pos.append([nx, ny, target_dir])

        # 아무 냄새 없는 칸이 있으면 해당 칸으로 이동
        if board[nx][ny] == 0 or len(board[nx][ny]) == 0:
            n_shark_pos = [nx, ny]
            n_direction = target_dir

            # 일단 이동 시킴
            n_board[nx][ny].append(shark_num)
            
            return n_shark_pos, n_direction

    # 주위에 아무 냄새 없는 칸이 없으면 자신의 냄새가 있는 칸으로 이동
    # -> 기록한 배열에서 가장 앞이 우선순위가 가장 높았던 위치
    n_board[now_shark_smell_pos[0][0]][now_shark_smell_pos[0][1]].append(shark_num)
    return [now_shark_smell_pos[0][0], now_shark_smell_pos[0][1]], now_shark_smell_pos[0][2]


# 겹친 상어 처리 및 살아남은 상어 냄새 기록
def check_dup_and_record_smell(now_time):
    global n_board

    # 삭제할 상어 기록
    delete_shark_num = []
    # 모든 위치 확인
    for i in range(N):
        for j in range(N):
            # 상어가 있는 위치라면
            if len(n_board[i][j]) >= 1:
                # 맨 앞에 있는 상어의 냄새만 기록 
                # -> 1번 상어부터 차례로 이동시키고 기록했기 때문에 맨 앞 상어가 가장 작은 번호의 상어
                board[i][j] = [n_board[i][j][0], now_time]  # 냄새 기록
                check[i][j] = n_board[i][j][0]  # 상어 위치 기록
                # 그 뒤의 상어들은 삭제 리스트에 추가, 살아있는 상어 리스트에서 제거
                for k in range(1, len(n_board[i][j])):
                    shark_now_pos[n_board[i][j][k]] = []  # 살아있는 상어 위치 저장한 배열에서 제거
                    shark_now_dir[n_board[i][j][k]] = 0  # 방향도 0으로 바꿈(삭제된 거랑 같은 효과)
					# 삭제할 상어에 기록함
                    delete_shark_num.append(n_board[i][j][k])
                    
	# 모든 위치 확인하며 삭제할 상어는 상어 위치 기록한 배열에서 제거
    for i in range(N):
        for j in range(N):
            if check[i][j] in delete_shark_num:
                check[i][j] = 0


# 모든 상어를 이동시키는 함수
def move_all_shark(now_time):
    global board
	# 1번부터 M번까지 상어를 차례로 이동시킴
    for num in range(1, M + 1):
        # 현재 상어의 현재 위치
        shark_pos = shark_now_pos[num]
        # 현재 상어가 격자 안에 있는지 체크 -> 없으면 넘어감
        if len(shark_pos) == 0:
            continue
		
        now_dir = shark_now_dir[num]  # 현재 상어 방향
        now_dir_priority = shark_priority_info[num][now_dir]  # 현재 상어 방향에 맞는 방향 우선순위

        # 현재 상어 일단 이동 시킴
        n_shark_pos, n_direction = check_shark_move_pos(num, shark_pos, now_dir, now_dir_priority)

        # 일단 다른 상어랑 겹치는건 생각 안하고 기록 함 -> 나중에 겹쳐서 제거될 때 제거함
        shark_now_dir[num] = n_direction
        shark_now_pos[num] = n_shark_pos
	
    # 겹친 상어 처리 및 살아남은 상어 냄새 기록
    check_dup_and_record_smell(now_time)


# 오래된 냄새 제거하는 함수
def erase_smell(now_time):
    global board
    # 제거해야 하는 냄새 시간 -> 현재 시간에서 냄새가 기록된 시간을 빼서 구한다.
    target_smell_time = now_time - K
    # 모든 위치를 확인해서 제거할 수 있는 냄새 제거
    for i in range(N):
        for j in range(N):
        	# 냄새가 없는 위치면 다음 위치로 넘어감
            # board[i][j] == 0 -> 처음에 배열 생성할 때 0으로 초기화 했어서 추가함
            if board[i][j] == 0 or len(board[i][j]) == 0:
                continue
            # 냄새는 [상어 번호, 냄새가 기록된 시각] 으로 저장돼있음
            smell = board[i][j]
            if smell[1] <= target_smell_time:
            	# 빈 칸으로 바꿈 -> 냄새 제거됨
                board[i][j] = []


# 종료 가능한지 확인하는 함수
def is_finish():
	# 1번 제외한 상어가 남아있는지 확인 -> 제외된 상어는 빈 배열([])만 남아있는다.
    for k in range(2, M + 1):
        if len(shark_now_pos[k]) > 0:
            return False
    return True


# 시뮬레이션 시작
answer = -1  # 정답
time = 1  # 시간
while time <= 1000:
	# 상어가 이동한 상태 저장할 배열(겹치는 상어 제거 전)
    n_board = [[[] for _ in range(N)] for _ in range(N)]
	# 모든 상어 이동
    move_all_shark(time)
	# 시간에 따라 냄새 제거
    erase_smell(time)
	# 시뮬레이션이 종료될 수 있는지 확인
    if is_finish():
        answer = time
        break

    time += 1

print(answer)

정리

• 상어가 동시에 이동하는 상황을 처리하는 부분에서 시간이 오래걸렸다.