시추 작업 (Boring Business)

시추(boring)는 땅속에 터널, 우물, 구멍을 뚫는 굴착 작업을 말한다. 지오스티어링(geosteering) 기법을 쓰면 굴착 기사는 우물을 수직으로도, 수평으로도, 심지어 비스듬한 각도로도 파 내려갈 수 있다.

굴착을 시작하기 전에 우물 설계도(well plan)를 만든다. 이는 앞으로 뚫을 우물의 기하학적 모양을 나타내는 선분들의 순서열이다. 굴착이 진행되며 새로운 정보가 들어오면 설계도는 갱신되고 계획이 수정될 수 있다.

여러분의 과제는 시추공(borehole)이 자기 자신과 교차하지 않는지 확인하여 우물 설계도가 유효한지 검증하는 프로그램을 작성하는 것이다. 우물 설계도는 2차원 평면 위 시추공의 수직 단면을 나타내며, 시추 지점(드릴)은 항상 정수 좌표 위에서 한 칸씩 움직인다.

이미 뚫려 있는 시추공(아래 그림)은 다음 정수 좌표들을 순서대로 잇는 꺾인 선이다.

(0, -1) → (0, -3) → (3, -3) → (3, -5) → (5, -5) → (5, -3) → (7, -3) → (7, -7) → (-1, -7) → (-1, -5)

즉 시추공은 (0, -1)에서 시작해 (-1, -5)에서 끝난다. 시추공은 이 선이 지나는 모든 정수 격자점의 집합이다. 여러분의 프로그램은 이 시추공의 끝점인 (-1, -5)에서 굴착을 이어서 진행하며, (-1, -5)는 이미 시추공의 일부이다.

입력은 굴착 명령 쌍들의 순서열이다. 각 굴착 명령 쌍은 네 방향 지시자 중 하나로 시작하고, 그 뒤에 양의 정수 길이가 온다.

• d: 아래(down) — y가 감소
• u: 위(up) — y가 증가
• l: 왼쪽(left) — x가 감소
• r: 오른쪽(right) — x가 증가

이와 별개로 q(quit) 뒤에 아무 정수나 오는 명령이 있으며, 이는 프로그램이 실행을 멈춰야 함을 뜻한다.

입력은 드릴이 다음 조건을 항상 만족하도록 주어진다고 가정해도 좋다.

• 지면 위로 올라가지 않는다.
• 지면에서 200단위보다 더 깊이 내려가지 않는다.
• 최초 시작점에서 왼쪽으로 200단위보다 더 멀리 가지 않는다.
• 최초 시작점에서 오른쪽으로 200단위보다 더 멀리 가지 않는다.

프로그램은 그림의 우물이 이미 뚫려 있다고 가정하고 굴착을 이어서 감시한다. 앞서 말했듯 (-1, -5)가 프로그램의 시작 위치이다.

각 명령마다 드릴은 주어진 방향으로 주어진 길이만큼 한 칸씩 전진한다. 이 이동 도중 드릴이 이미 시추공에 속한 정수 격자점에 들어서면 자기 교차가 발생한 것이다.

각 명령을 처리한 뒤, 새 위치의 x좌표와 y좌표를 공백으로 구분해 출력하고, 그 뒤에 safe 또는 DANGER를 한 줄로 출력한다. 이번 이동에서 기존 시추공과 한 번도 만나지 않았다면 safe, 한 번이라도 만났다면 DANGER이다. 출력하는 좌표는 명령을 끝까지 수행한 뒤의 위치이다. 자기 교차를 감지해 DANGER를 출력한 후에는 프로그램을 멈춘다.