[알고리즘] 미생물 격리

포인트

• 처음에는 2차원 맵에서 처리를 하는데 시간 초과가 걸려서 다시 초기화를 하는 방향으로 풀었다. 생각보다 이런 방법을 쓸 수 있구나 생각하니 편한 것 같다.
• 처음 10~15분으로 손코딩을 하면서 문제를 익숙해져 보자; 새롭게 보인다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python

import sys

sys.stdin = open('input.txt')
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def change_dir(dir: int) -> int:
	if dir == 0:
		return 1
	elif dir == 1:
		return 0
	elif dir == 2:
		return 3
	elif dir == 3:
		return 2


for test in range(1, int(input()) + 1):
	n, m, k = map(int, input().split())
	# n*n
	# m 은 시간
	# k는 군집의 수
	viruses = []
	for _ in range(k):
		i, j, num, dir = map(int, input().split())
		dir -= 1
		viruses.append([i, j, num, dir])
	
	while m:
		m -= 1
		copy = dict()
		for virus in viruses:
			x, y, num, dir = virus
			nx, ny = x + dx[dir], y + dy[dir]
			if nx == 0 or ny == 0 or nx == n - 1 or ny == n - 1:
				a = num // 2
				if a:
					if (nx, ny) not in copy:
						copy[(nx, ny)] = [[a, change_dir(dir)]]
					else:
						copy[(nx, ny)].append([a, change_dir(dir)])
			else:
				if (nx, ny) not in copy:
					copy[(nx, ny)] = [[num, dir]]
				else:
					copy[(nx, ny)].append([num, dir])
		
		### copy map 을 만들었다.
		viruses.clear()
		for key, value in copy.items():
			if len(value) >= 2:
				temp = sorted(value, reverse=True)
				temp_num = sum(map(lambda x: x[0], temp))
				viruses.append([key[0], key[1], temp_num, temp[0][1]])
			else:
				viruses.append([key[0], key[1], value[0][0], value[0][1]])
	
	result = sum(map(lambda x: x[2], viruses))
	
	print('#{} {}'.format(test, result))