시뮬레이션 2

격자 안에서의 완전탐색

• 최적화 아이디어
  • 각 직사각형의 동전의 크기 채우기
  • 사각형을 구할 때 기존에 구해 둔 배열로 동전 개수 구하기
  • DP느낌

격자 안에서 밀고 당기기

• 가로, 혹은 세로로 이동하는 경우
  1. 미는 방향의 반대에서 당겨오기(1, 2, 3, 4로 밀면 4, 3, 2, 1 순서로 당기기)
  2. 배열 하나 더 만들기

격자 안에서 떨어지는 경우

• 아래부터 읽으면서 0이 아닌 것을 새 추가하기

• 기존 배열을 0으로 채우기

• 새 배열의 값을 기존 배열에 넣어주기

• 행 순서가 아닌 열 순서로 읽는 경우가 많음

• 벽이 있는 경우?

  • 벽 위에 있는 숫자들은 벽 위까지 중력 작용
  • 벽 아래 있는 숫자들은 바닥까지 중력 작용

for j in range(6):
	idx = n - 1
	while idx > 0:
		nxt = -1
		tmp = []
		for i in range(idx, -1, -1):
			if arr[i][j] == -1:
				nxt = i - 1
				break
			if arr[i][j] != 0:
				tmp.append(arr[i][j])
		
		i = idx
		while i >= 0:
			if arr[i][j] == -1:
				break
			arr[i][j] = 0
			i -= 1

		for i in range(len(tmp)):
			arr[idx - i][j] = tmp[i]
	
		idx = nxt
for i in range(6):
	print(*arr[i])

격자 안에서 여러 객체를 이동

객체들이 각자 이동하는 경우

• 순차 이동
• 한번에 이동

차이: 개체끼리의 상호작용시 차이남

한번에 이동 $\rightarrow$ 배열을 추가해서 이동 결과를 적어놓을 필요 다음 상태를 구해놓은 뒤 처리