# 방향 이동에 사용할 인덱스 벡터 정의
# 문제조건에서 '1: 상, 2: 하, 3: 좌, 4: 우 '라는 조건을 고려하면,
# 델타를 다음과 같이 설정할 수 있다.
di, dj = [0,-1,1,0,0], [0,0,0,-1,1]
# 방향 이동 인덱스 벡터(di, dj) 정의:
# di, dj는 각각 y축(세로, 행 i 변화량), x축(가로, 열 j 변화량)
# 이동을 위한 인덱스 변화량을 정의합니다.
# di[1] == -1은 '상' 방향 이동 시 행 번호를 1 감소시키라는 의미입니다(위로 이동).
# dj[4] == 1은 '우' 방향 이동 시 열 번호를 1 증가시키라는 의미입니다(오른쪽으로 이동).
# 방향을 반대로 바꿀 때 사용할 테이블
tbl = [0, 2, 1, 4, 3]
# 문제조건에서 '1: 상, 2: 하, 3: 좌, 4: 우 '가 원래 방향이었다.
# 하지만 경계를 마주했을 경우, 방향을 바꾸는데, 그 때를 위한 테이블이 tbl이다!
###########################################################################
# 방향 전환 테이블(tbl) 정의:
# tbl 배열은 군집이 경계에 도달했을 때 이동 방향을 반대로 바꾸기 위한 매핑을 제공합니다.
# 예를 들어, '상(1)' 방향 이동 중 경계에 도달하면 '하(2)'로 방향을 바꾸어야 하므로, tbl[1] == 2.
# 이동 처리 로직:
# 군집의 현재 위치(arr[i][0], arr[i][1])와 이동 방향(arr[i][3])을 사용하여,
# di, dj 배열을 참조하여 다음 위치를 계산합니다.
# 이 때, arr[i][3]은 현재 방향을 나타내며, di[arr[i][3]], dj[arr[i][3]]를 사용하여
# 다음 행과 열의 위치를 업데이트합니다.
#########################################################################
# 테스트 케이스 개수를 입력받음
T = int(input())
for test_case in range(1, T + 1):
# N: 격자 크기, M: 이동 횟수, K: 미생물 군집의 수
N, M, K = map(int, input().split())
# 미생물 군집의 정보를 입력받아 저장
arr = [list(map(int, input().split())) for _ in range(K)]
# 이 때 각 줄 마다, i: 행, j: 열, n: 미생물 개수, dr: 방향 (각 군집마다 정보들을 입력해준다!)
# 이 정보들을 미생물 군집의 수만큼 넣어줘야겠지?...
for _ in range(M):
# [1] 1칸 이동 처리
for i in range(len(arr)):
# 각 미생물 군집들을 순회한다...!
# (arr는 군집들의 정보가 들어있는 2차원 배열이니까!)
# arr[i][3] 방향으로 이동 처리 (이 때, [3]은 방향이니까!)
# 해석에서 상당히 주의해야하는 부분!
arr[i][0] = arr[i][0] + di[arr[i][3]]
# i: i번째의 미생물 군집, di는 행의 이동을 의미!
arr[i][1] = arr[i][1] + dj[arr[i][3]]
# i: i번째의 미생물 군집, dj는 열의 이동을 의미!
# 경계 도달 시 처리:
# 이동 후 군집의 위치가 격자의 경계에 해당하는지 확인합니다. 경계는 행 또는 열의 값이 0 또는 N-1일 때입니다.
# 경계에 도달하면, 군집의 미생물 수(arr[i][2])를 반으로 줄이고,
# 현재 방향(arr[i][3])을 tbl 배열을 사용하여 반대 방향으로 업데이트합니다.
# 경계에 도달하면 미생물 수를 반으로 줄이고 방향을 반대로 바꿈
if arr[i][0] == 0 or arr[i][0] == N-1 or arr[i][1] == 0 or arr[i][1] == N-1:
arr[i][2] //= 2 # arr[i][2] = '미생물 수', 절반이 된다.
arr[i][3] = tbl[arr[i][3]] # 경계션과 충동하면 tbl을 이용해 방향을 바꿈
# [2] 미생물 수 내림차순으로 정렬(같은 위치에 있을 때 큰 군집이 흡수하기 위함)
arr.sort(key=lambda x: (x[0], x[1], x[2]), reverse=True)
# 여기서 x는 lambda 함수에 의해 참조되는 각 요소를 의미합니다. lambda 함수는 sort 메서드의 key 인수로 사용되며,
# 이 lambda 함수는 arr 리스트의 각 요소를 x로 받아 처리합니다.
# sort 메서드의 기본 구조
# sort(*, key=None, reverse=False)는 파이썬 리스트의 내장 메서드입니다. key 매개변수는 정렬 기준을 지정하며,
# reverse 매개변수는 정렬 순서를 역순(내림차순)으로 할지를 결정합니다.
# Notice: 이 때, *의 의미는??
# * 기호는 파이썬 함수 정의에서 키워드 전용 인수(keyword-only arguments)를 지정할 때 사용됩니다.
# 이 기호의 사용은 해당 위치 이후에 오는 인수들이 반드시 키워드 인수로 전달되어야 함을 의미합니다.
# 즉, 이들 인수는 위치에 기반한 인수 전달 방식을 사용할 수 없고, 이름을 명시해서 전달해야 합니다.
# sort(*, key=None, reverse=False)에서 *는 key와 reverse 인수가 키워드 인수로만 지정될 수 있음을 나타냅니다.
# 이는 sort 함수를 호출할 때, key와 reverse 매개변수에 대해 값을 지정하려면,
# 이들의 이름을 명시적으로 적어주어야 함을 의미합니다. 위치를 통한 인수 전달이 허용되지 않습니다.
# key=lambda x: (x[0], x[1], x[2])의 의미
# key 매개변수에 lambda 함수를 사용해 정렬 기준을 제공합니다.
# 여기서 x는 arr 리스트의 각 요소를 나타내며, 각 요소는 [i, j, n] 형태의 리스트입니다
# (여기서 i는 행 위치, j는 열 위치, n은 미생물 수를 의미).
# lambda x: (x[0], x[1], x[2])는 정렬 시
# 각 요소의 첫 번째 요소(x[0], 행 위치), 두 번째 요소(x[1], 열 위치), 세 번째 요소(x[2], 미생물 수) 순으로
#'우선순위'를 두고 정렬하라는 의미입니다.
# [3] 같은 위치에 있는 미생물 군집들을 합침
i = 1
while i < len(arr):
# 같은 위치에 있는 경우
if arr[i-1][0:2] == arr[i][0:2]: # arr가 정렬된 상태이므로,
# 앞 군집이 뒤 군집을 흡수(정렬에 따라, 더 큰 군집이 앞자리에 위치하므로([i-1]))
arr[i-1][2] += arr[i][2] # # arr[i][2] = '미생물 수', 절반이 된다.
# 뒤 군집을 리스트에서 제거
arr.pop(i)
# (중요!)뒤 군집을 제거하고, i의 값은 증가하지 않습니다(다음 군집이 현재 인덱스로 이동하기 때문).
# 예시: [[2, 2, 200], [2, 2, 100], [1, 3, 50], [1, 3, 30]] 가 초기 데이터일 경우!
# i=1일 때:
# arr[0][0:2] == arr[1][0:2] (두 군집의 위치가 같음, (2, 2)).
# 앞 군집(arr[0][2], 미생물 수 = 200)이 뒤 군집(arr[1][2], 미생물 수 = 100)을 흡수합니다.
# 결과: arr[0][2] = 300 (200 + 100).
# 뒤 군집을 제거하고, i의 값은 증가하지 않습니다(다음 군집이 현재 인덱스로 이동하기 때문).
# i=1일 때 (계속): (while문의 특성으로 인해 다시 i=1로 돌아옴...!)
# 군집 2가 제거된 후의 상태를 확인합니다.
# 이제 arr는 [[2, 2, 300], [1, 3, 50], [1, 3, 30]] 상태입니다.
# 다음 군집 ([1, 3, 50])과 현재 군집 ([2, 2, 300])의 위치가 다릅니다.
# i를 1 증가시켜 i=2로 만듭니다. (else문을 따라서!)
# i=2일 때:
# 현재 군집(arr[1][0:2], 위치 (1, 3))과 다음 군집(arr[2][0:2], 위치 (1, 3))의 위치가 같습니다.
# 앞 군집(arr[1][2], 미생물 수 = 50)이 뒤 군집(arr[2][2], 미생물 수 = 30)을 흡수합니다.
# 결과: arr[1][2] = 80 (50 + 30).
# 뒤 군집을 제거하고, i의 값은 증가하지 않습니다.
# 이제, arr는 [[2, 2, 300], [1, 3, 80]] 상태이며, 더 이상 비교할 군집이 없습니다
# (i=2 이후 arr의 길이는 2이므로, while 조건 i < len(arr)을 만족하지 않음).
else:
i += 1 # 다음 위치의 군집을 체크하러 가자.
# 모든 미생물 군집의 수를 합산
ans = 0
for lst in arr:
ans += lst[2]
# 결과 출력
print(f'#{test_case} {ans}')
댓글남기기