충전 케이블 개수

200점케이스 15출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

한 주차장은 가로로 M칸, 세로로 N칸인 격자 모양이다. 각 칸에는 차 한 대를 세울 수 있다. 칸의 위치는 가로 좌표와 세로 좌표로 나타내는데, 가로 좌표는 왼쪽부터 0 이상 M-1 이하의 정수이고 세로 좌표는 위쪽부터 0 이상 N-1 이하의 정수다.

이 주차장에는 전기차 K대가 세워져 있고, 관리인은 세워져 있는 전기차를 모두 충전해 주어야 한다. 충전 케이블은 릴에 감겨 있는데, 하나의 릴에서 뽑은 케이블은 가로나 세로로 바로 붙어 있는 칸까지 이어서 쓸 수 있다. 그래서 가로나 세로로 서로 붙어 있는 전기차들은 릴 하나로 모두 충전할 수 있다. 붙어 있는 차가 여러 대 줄지어 이어져 있어도 케이블을 차례대로 이어 가면 되므로 릴 하나로 충분하다. 반면 대각선으로만 붙어 있는 두 전기차는 릴 하나로 함께 충전할 수 없다.

전기차의 위치가 주어졌을 때, 전기차를 모두 충전하기 위해 필요한 릴의 최소 개수를 계산하는 프로그램을 작성하여라. 관리인은 이 일을 여러 날에 걸쳐 하므로, 서로 다른 날의 주차 상태가 T개 주어지고 각 날마다 답을 구해야 한다.

예를 들어 가로 M=5칸, 세로 N=3칸인 주차장에 전기차 K=3대가 세워진 하루를 생각해보자. 세 대의 위치는 다음의 표와 같다.

차 번호	1	2	3
가로 좌표	2	3	0
세로 좌표	1	2	1

이 주차 상태를 주차장 모양에 그대로 옮기면 다음과 같다. 표에서 V는 전기차가 세워진 칸이다.

칸	가로 0	가로 2	가로 3
세로 0
세로 1	V	V
세로 2			V

세 대의 전기차는 어느 두 대도 가로나 세로로 붙어 있지 않다. 가로 0, 세로 1의 차와 가로 2, 세로 1의 차는 같은 세로 좌표에 있지만 가운데 한 칸이 비어 있어 서로 떨어져 있다. 또한 가로 2, 세로 1의 차와 가로 3, 세로 2의 차는 대각선으로만 붙어 있어 릴을 함께 쓸 수 없다. 따라서 릴을 세 개 써야 하고, 이 날의 정답은 3이다.

입출력 예시

예시 1

입력

출력

예시 2

입력

출력

1
1

예시 3

입력

1
1 1 1
0 0

출력

입력 조건

가장 먼저 첫째 줄에 주차 상태의 개수 T가 주어진다. T는 1 이상 10 이하의 자연수다.
이어서 T개의 주차 상태가 차례대로 주어진다.
각 주차 상태의 첫째 줄에는 주차장의 가로 칸 수 M과 세로 칸 수 N, 그리고 전기차의 대수 K가 공백을 두고 주어진다. M과 N은 각각 1 이상 50 이하의 자연수이고, K는 1 이상 M과 N을 곱한 값 이하의 자연수다.
이어서 K개의 줄에 걸쳐 각 전기차가 세워진 칸의 가로 좌표와 세로 좌표가 공백을 두고 주어진다. 가로 좌표가 먼저 오고 세로 좌표가 뒤에 온다. 가로 좌표는 0 이상 M-1 이하의 정수이고, 세로 좌표는 0 이상 N-1 이하의 정수다. 같은 칸이 두 번 주어지지는 않는다.

출력 조건

T개의 주차 상태에 대하여, 전기차를 모두 충전하기 위해 필요한 릴의 최소 개수를 한 줄에 하나씩 차례대로 출력한다. 주차 상태가 주어진 순서를 그대로 지킨다.

요구사항

가로나 세로로 붙어 있는 전기차들은 릴 하나로 함께 충전합니다
대각선으로만 붙어 있는 두 전기차는 릴 하나로 함께 충전할 수 없습니다
각 칸의 위치는 가로 좌표가 먼저, 세로 좌표가 뒤에 주어집니다
주차 상태마다 답을 한 줄에 하나씩 출력합니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 15개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

입력

기대 출력

1
1 1 1
0 0

1
1

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 3.0ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.