도색 로봇의 최종 색상 분포

문제

도색 로봇이 격자 모양 패널을 칠합니다. canvas[r][c]는 r행 c열 칸의 현재 색상 번호입니다.

로봇은 작업 지시 strokes를 앞에서부터 순서대로 수행합니다. strokes[i] = [r, c, color]는 다음을 뜻합니다.

(r, c) 칸에서 출발해, 그 칸과 같은 색이면서 상하좌우로 이어진 칸 전체를 color로 칠한다.

이어짐은 상하좌우 네 방향만 따지며, 대각선으로만 닿은 칸은 이어진 것으로 보지 않습니다. 출발 칸의 색이 이미 color와 같다면 아무것도 바뀌지 않습니다. 또한 앞선 지시로 칠해진 결과 위에 다음 지시가 적용됩니다.

모든 지시를 수행한 뒤 패널에 남아 있는 색상별 칸 수를 반환하는 solution(canvas, strokes) 함수를 작성하세요. 반환값은 [색상 번호, 칸 수] 쌍의 배열이며, 색상 번호 오름차순으로 정렬합니다. 패널에 한 칸도 없는 색상은 포함하지 않습니다.

예시

패널이 다음과 같고 strokes = [[0, 0, 5], [2, 0, 2]]일 때,

1 1 2
1 2 2
3 3 2

1. 첫 지시: (0,0)의 색 1과 이어진 (0,0), (0,1), (1,0)이 5가 됩니다.

5 5 2
5 2 2
3 3 2

2. 둘째 지시: (2,0)의 색 3과 이어진 (2,0), (2,1)이 2가 됩니다.

5 5 2
5 2 2
2 2 2

남은 색은 2가 6칸, 5가 3칸이므로 결과는 [[2, 6], [5, 3]]입니다.

세 번째 예시 설명: 지시가 없으면 처음 패널을 그대로 세면 됩니다.

네 번째 예시 설명: 첫 지시로 윗줄이 2가 되면서 패널 전체가 2로 이어지고, 둘째 지시가 그 전체를 3으로 덮어 3이 4칸이 됩니다.

제약 조건

• 1 ≤ canvas.length, canvas[0].length ≤ 100, 모든 행의 길이는 같습니다.
• 0 ≤ canvas[r][c] ≤ 1,000
• 0 ≤ strokes.length ≤ 50
• strokes[i] = [r, c, color]이며 (r, c)는 항상 패널 안의 좌표, 0 ≤ color ≤ 1,000

시간 복잡도 목표: O(strokes.length × 행 × 열)

공간 복잡도 목표: O(행 × 열)