20056: 마법사 상어와 파이어볼

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

20056번: 마법사 상어와 파이어볼

설명

이 문제 역시 이어진 격자문제이다. "격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다."

출처: https://jennnn.tistory.com/77

핵심 아이디어

• 문제에 주어진 요구조건을 그대로 따라하면 되는 시뮬레이션 문제
• 8가지 방향 고려
• 이어진 격자 고려

크기가 N x N 인 2차원 배열 만들기. 각 요소는 빈 리스트로 초기화 된다. 이는 보통 'n' 개의 노드를 가진 그래프의 인접 리스트를 표현할 때 사용. 여기서 각 노드는 0부터 'n-1'까지의 인덱스를 가지고, 각 노드에 연결된 다른 노드들의 정보를 저장하기 위해 빈 리스트를 사용한다.

graph = [[[] for _ in range(n)] for _ in range(n)]
for i in graph:
	print(i)
# 출력 값
[[], [], [], []]
[[], [], [], []]
[[], [], [], []]
[[], [], [], []]

 

r예시 1번, 입력: r,c,m,s,d

(1,1) 파이어볼은 속력이 2이므로 2번 방향으로 두 칸가고, (1,4)파이어볼은 속력이 1이므로 6번 방향으로 1칸 이동한다. 그후 (1,3)에서 두 개 이상의 파이어볼이 만났으므로, [2-1]조건에 의해 하나의 파이어볼로 합친다. 그리고 나서 [2-2]조건대로 4개의 파이어볼로 나눈다. 따라서 각 4개의 파이어볼의 질량은 (5+7) / 5 = 2이고, 방향은 합쳐지는 파이어볼 방향이 2, 6으로 모두 짝수이다. 따라서 0,2,4,6이 된다. 질량의 합은 총 8이다. 

코드 구현

n, m, k = map(int, input().split())
# x, y, m, s, d
fireball = []
for _ in range(m):
	r,c,m,s,d = list(map(int, input().split()))
	fireball.append([r-1,c-1,m,s,d])
# 파이어볼의 질량, 속도, 방향 저장
graph = [[[] for _ in range(n)] for _ in range(n)]
# 8가지 방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

for _ in range(k): # k회 명령하기
	while fireball:
		x,y,m,s,d = fireball.pop(0)
		# 1. 파이어볼 이동하기
		nx = (x + dx[d] * s) % n
		ny = (y + dy[d] * s) % n
		graph[nx][ny].append([m,s,d])
	# 2. 파이어볼이 2개인지 확인하기
	for i in range(n):
		for j in range(n):
			if len(graph[i][j]) > 1: # 2개 이상이면 4개의 파이어볼로 쪼개기
				# 2-1 파이어볼 합치기
				new_m = 0
				new_s = 0
				# (i,j)에 있는 파이어볼의 개수
				count = len(graph[i][j])
				odd = 0
				even = 0
				while graph[i][j]:
					mm, ss, dd = graph[i][j].pop(0)
					new_m += mm
					new_s += ss
					if dd % 2 == 0:
						even += 1
					else:
						odd += 1
				if new_m // 5:
					if even == count or odd == count:
						# 0, 2, 4, 6
						for d in [0,2,4,6]:
							fireball.append([i,j, new_m // 5, new_s // count, d])
					else:
						# 1, 3, 5, 7
						for d in [1,3,5,7]:
							fireball.append([i,j, new_m // 5, new_s // count, d])
			if len(graph[i][j]) == 1:
				fireball.append([i,j] + graph[i][j].pop(0))

ans = 0
for i in fireball:
	ans += i[2]
print(ans)

참고 블로그

https://jennnn.tistory.com/77

[백준] 20056. 마법사 상어와 파이어볼 / python 파이썬