19237: 어른 상어

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

19237번: 어른 상어

설명

예시

상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 한다. 1의 번호를 가진 어른 상어가 가장 강력해서 모두를 쫒아낼 수 있다. 

• 맨 처음에 모든 상어가 자신의 위치에 자신의 냄새(smell)를 뿌린다. 
• 그 후 1초마다 모든 상어가 동시에 상하좌우 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다.
• 냄새는 상어가 k번 이동하고 나면 사라진다.
• 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 이때, 가능한 칸이 여러개 일 수 있는데, 그 경우에는 특정한 우선순위를 따른다.
• 우선 순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨처음 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다. 
• 인접한 칸 중에 아무 냄새도 없는 칸이 없으면 자신의 냄새가 들어있는 칸으로 이동한다. 
• 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두를 격자 밖으로 쫒아낸다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램 작성하시오.

핵심 아이디어

매 초마다 모든 상어를 이동시키며 요구하는 기능을 정해진 내용대로 처리하는 전형적인 시뮬레이션 문제. 상어마다 방향 우선순위 정보가 주어진다. 따라서 상어마다 서로 다른 방향으로 이동하기 때문에, 모든 방향 정보를 담을 리스트를 별로도 선언해야 한다. 

• 구현, 시뮬레이션 문제로 요구 사항에 맞게 구현하면 풀리는 문제다.
• priorities: 미리 정해진 방향 정보를 저장할 리스트
• smell: 현재 시간에 냄새의 상황을 보여주는 리스트
• data: 상어의 현재 위치를 나타내는 리스트
• 단, 1000초를 넘어가면 -> 1000를 포함해서 해서 계산해 주어야한다. 

update_smell(): 모든 냄새 정보를 업데이트 하는 함수. 각 위치를 확인하며 냄새가 남아 있는 경우 1만큼 감소시키고, 상어가 위치한 곳은 [상어번호, 초기냄새(k)] 를 삽입하기

move(): 모든 상어를 이동시키는 함수. 이동한 결과를 담을 임시 테이블을 선언해준다. 각 위치를 확인하며 상어가 존재하면 방향 우선순위에 따라서 해당 방향으로 이동한다. 일단 이동하려는 곳에 냄새가 존재하는지 확인한다. 만약 냄새가 없다면 해당 방향으로 상어 이동시키기 하지만 만약 이미 다른 상어가 있다면 번호가 낮은 상어가 들어가도록 한다. 그리고 상하좌우 주변에 냄새가 모두 남아 있다면, 자신의 냄새가 있는 곳으로 이동한다.

코드 구현

n, m, k = map(int, input().split())
# 모든 상어의 위치와 맵 입력받기
data = [list(map(int, input().split())) for _ in range(n)]
# 상어의 초기 방향 정해주기
directions = list(map(int, input().split()))
# 상어의 상황별 우선순위 받아오기 (위 아래 왼쪽 오른쪽)
priorities = [[] for _ in range(m)]
for i in range(m):
	for j in range(4):
		priorities[i].append(list(map(int, input().split())))
# for i in priorities:
# 	print(i)

# 상어 이동을 위한 방향 정의
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 각 상어마다 [특정 냄새의 상어 번호, 특정 냄새의 남은 시간]을 저장하는 2차원 리스트
smell = [[[0,0]] * n for _ in range(n)]

# 모든 냄새 정보 업데이트
def update_smell():
	# 각 위치를 확인하며
	for i in range(n):
		for j in range(n):
			# 냄새가 남아 있는 경우, 1만큼 감소시키기
			if smell[i][j][1] > 0:
				smell[i][j][1] -= 1 # 한칸 이동할 때 마다 냄새 줄어든다.
			# 상어가 존재하는 위치의 경우, 해당 위치의 냄새를 k로 설정
			if data[i][j] != 0:
				# 상어 번호, 냄새 머무는 초기시간 삽입
				smell[i][j] = [data[i][j], k]
# 모든 상어 이동시키는 함수
def move():
	# 이동 결과를 담기 위한 임시 테이블 초기화
	new_data = [[0] * n for _ in range(n)]
	# 각 위치를 하나씩 확인하며
	for x in range(n):
		for y in range(n):
			# 상어가 존재하면
			if data[x][y] != 0: # 상어의 위치라는 뜻
				# 방향 1 ~ 4 이지만 컴터는 0 ~ 3
				# 현재 상어의 방향
				direction = directions[data[x][y] - 1] # index 재조정
				flag = False # 초기화
				# 일단 냄새가 존재하지 않은 곳이 있는지 확인
				for index in range(4):
					nx = x + dx[priorities[data[x][y]-1][direction-1][index]-1]
					ny = y + dy[priorities[data[x][y]-1][direction-1][index]-1]
					if (0<=nx<n) and (0<=ny<n):
						# 냄새가 나지 않는 곳이라면 1순위
						if smell[nx][ny][1] == 0:
							# 해당 상어의 방향 이동시키기
							directions[data[x][y]-1] = priorities[data[x][y]-1][direction-1][index]
							# 상어 이동 시키기
							if new_data[nx][ny] == 0:
								new_data[nx][ny] = data[x][y]
							else: # 만약 이미 다른 상어가 있다면 번호가 낮은 상어가 들어가도록
								new_data[nx][ny] = min(data[x][y], new_data[nx][ny])
							flag = True
							break
				if flag:
					continue
				# 주변에 모두 냄새가 남아 있다면, 자신의 냄새가 있는 곳으로 이동
				for index in priorities[data[x][y] - 1][direction - 1]:
					nx = x + dx[index -1]
					ny = y + dy[index -1]
					if (0<=nx<n) and (0<=ny<n):
						# 자신의 냄새가 있는 곳이라면
						if smell[nx][ny][0] == data[x][y]:
							# 해당 상어 방향 변경
							directions[data[x][y]-1] = index
							# 상어 이동시키기
							new_data[nx][ny] = data[x][y]
							break
	return new_data

time = 0 # 0초 부터 시작
while True:
	update_smell() # 모든 위치의 냄새 업데이트
	new_data = move() # 모든 상어를 이동시키기
	data = new_data # 맵 업데이트
	time += 1 # 시간 증가

	# 1번 상어만 남았는지 확인
	check = True
	for i in range(n):
		for j in range(n):
			# 번호 1보다 큰게 있다면
			if data[i][j] > 1:
				check = False
	if check:
		print(time)
		break
	# 1000초가 지날 때까지 끝나지 않았다면
	if time >= 1000:
		print(-1)
		break