두더지가 우리 마당에 직사각형 격자 모양의 굴을 파 놓았습니다. 이 피해에 분노한 우리는 몇 마리의 테리어를 마당에 풀어 두더지를 잡도록 했습니다. 테리어들은 청각이 매우 예민하여 두더지 근처로 가기만 해도 매우 빠르게 굴을 파서 잡아낼 수 있습니다.
하지만 두더지는 테리어의 발걸음으로 인한 진동에 민감하게 반응하며 적극적으로 이를 피하려고 합니다.
우리는 테리어들을 마당에 풀었을 당시 두더지가 어디에 있었는지 알지 못합니다.
하지만 일정 시간 동안 테리어들의 움직임을 관찰했고, 아직 두더지는 잡히지 않았습니다.
이제 우리는 이 관찰 기록을 바탕으로, 두더지가 있을 수 있는 위치를 추론하는 프로그램을 작성해야 합니다.
🕵️♀️ 행동 규칙
관찰을 시작한 시점에서 두더지는 테리어가 있는 위치 또는 그 인접한 위치(상하좌우)에 없었다는 것만 알고 있습니다.
그 이후 매 시간마다 다음과 같은 순서로 일어납니다:
테리어들이 움직입니다 (이동하지 않거나 상하좌우로 한 칸 이동 가능)
그 후 두더지가 움직입니다 (이동하지 않거나 상하좌우로 한 칸 이동 가능)
그리고 다음 조건이 항상 적용됩니다:
어떤 시간 간격의 시작 또는 끝에서도, 또는 도중이라도, 테리어가 두더지와 같은 위치에 있거나 인접한 위치에 있다면, 두더지는 잡혔을 것입니다.
즉, 테리어와 두더지가같은 시점 또는 서로 이동 직전·이동 직후에 붙어 있거나 같은 자리에 있었다면, 그때 두더지는 잡혔어야 합니다.
하지만 우리는 두더지가 아직 잡히지 않았다는 사실을 알고 있습니다.
📥 입력
하나 이상의 관찰 세트(Observation Set) 가 주어집니다. 각 세트는 다음과 같은 형식으로 구성됩니다:
첫 줄: W L N T
W: 마당의 너비 (x 좌표 최댓값)
L: 마당의 길이 (y 좌표 최댓값)
N: 테리어의 수 (0 이상)
T: 관찰 시간 (1 이상)
그 다음 N줄에 걸쳐 테리어들의 위치 정보가 주어집니다.
각 줄에는 테리어의 (x, y) 위치가 시간 0부터 T-1까지 순서대로 2T개의 정수로 주어집니다.
좌표는 괄호나 쉼표 없이 공백으로 구분되어 있으며, 가능한 좌표는 (0, 0)부터 (W, L)까지입니다.
입력의 끝은 W L N T가 모두 0인 줄로 표시됩니다.
📤 출력
각 관찰 세트에 대해 다음 형식으로 출력합니다:
첫 줄:
Observation Set K
여기서 K는 현재 세트 번호입니다 (1번부터 시작).
가능한 두더지의 최종 위치가 하나 이상이라면, 다음 줄부터 가능한 모든 위치를 출력합니다:
srand 1년 전
🐾 문제
두더지가 우리 마당에 직사각형 격자 모양의 굴을 파 놓았습니다. 이 피해에 분노한 우리는 몇 마리의 테리어를 마당에 풀어 두더지를 잡도록 했습니다. 테리어들은 청각이 매우 예민하여 두더지 근처로 가기만 해도 매우 빠르게 굴을 파서 잡아낼 수 있습니다.
하지만 두더지는 테리어의 발걸음으로 인한 진동에 민감하게 반응하며 적극적으로 이를 피하려고 합니다.
우리는 테리어들을 마당에 풀었을 당시 두더지가 어디에 있었는지 알지 못합니다.
하지만 일정 시간 동안 테리어들의 움직임을 관찰했고, 아직 두더지는 잡히지 않았습니다.
이제 우리는 이 관찰 기록을 바탕으로, 두더지가 있을 수 있는 위치를 추론하는 프로그램을 작성해야 합니다.
🕵️♀️ 행동 규칙
관찰을 시작한 시점에서 두더지는 테리어가 있는 위치 또는 그 인접한 위치(상하좌우)에 없었다는 것만 알고 있습니다.
그 이후 매 시간마다 다음과 같은 순서로 일어납니다:
테리어들이 움직입니다 (이동하지 않거나 상하좌우로 한 칸 이동 가능)
그 후 두더지가 움직입니다 (이동하지 않거나 상하좌우로 한 칸 이동 가능)
그리고 다음 조건이 항상 적용됩니다:
즉, 테리어와 두더지가 같은 시점 또는 서로 이동 직전·이동 직후에 붙어 있거나 같은 자리에 있었다면, 그때 두더지는 잡혔어야 합니다.
하지만 우리는 두더지가 아직 잡히지 않았다는 사실을 알고 있습니다.
📥 입력
하나 이상의 관찰 세트(Observation Set) 가 주어집니다. 각 세트는 다음과 같은 형식으로 구성됩니다:
첫 줄:
W L N TW: 마당의 너비 (x 좌표 최댓값)L: 마당의 길이 (y 좌표 최댓값)N: 테리어의 수 (0 이상)T: 관찰 시간 (1 이상)그 다음
N줄에 걸쳐 테리어들의 위치 정보가 주어집니다.각 줄에는 테리어의
(x, y)위치가 시간 0부터 T-1까지 순서대로 2T개의 정수로 주어집니다.좌표는 괄호나 쉼표 없이 공백으로 구분되어 있으며, 가능한 좌표는
(0, 0)부터(W, L)까지입니다.입력의 끝은
W L N T가 모두 0인 줄로 표시됩니다.📤 출력
각 관찰 세트에 대해 다음 형식으로 출력합니다:
첫 줄:
여기서
K는 현재 세트 번호입니다 (1번부터 시작).가능한 두더지의 최종 위치가 하나 이상이라면, 다음 줄부터 가능한 모든 위치를 출력합니다:
출력 형식:
(x,y)각 줄에는 최대 8개씩 출력하며, 괄호 내부와 출력 사이에는 공백 없음
각 좌표쌍은 정확히 하나의 공백으로 구분
정렬 기준:
y 좌표가 작은 것이 먼저
y가 같다면 x 좌표가 작은 것이 먼저
가능한 위치가 하나도 없다면, 다음과 같이 출력합니다: