터치 미션
문제
N×N 보드판 위에 2개 이상의 타겟 지점이 있다. 보드판 위에 참가자가 위치한 곳은 "P"로 표시된다. 벽은 "X"로, 비어있는 공간은 "B"로 표시된다. 각 타겟 지점은 "O"로 표시된다. 참가자는 1명이며, 이 참가자는 1초에 인접한 상, 하, 좌, 우의 위치 중에서 한 칸으로 이동할 수 있다. 벽이 위치한 곳으로는 이동할 수 없으며, 비어 있는 공간 혹은 타겟 지점으로는 이동할 수 있다.
이때, 참가자는 터치 미션이 시작되면 자신이 도달할 수 있는 지점 중에서 가장 최단 거리가 먼 타겟 지점에 도달해야 미션을 클리어할 수 있다. 즉, 참가자는 도달할 수 있는 지점 중에서 가장 먼 지점을 터치해야 클리어할 수 있다. 도달할 수 없는 지점은 터치해야 할 지점에서 배제한다.
예를 들어, 아래의 N=6인 경우를 가정하자. (행, 열)의 형태로 위치를 나타낼 때, 현재 상황에서 (1, 2)가 가장 먼 타겟 지점이며 클리어에 7초가 필요하다. 행의 번호와 열의 번호는 1부터 시작한다고 가정하자.
| B | O | B | B | B | B |
|---|---|---|---|---|---|
| X | X | X | X | X | B |
| B | B | O | B | P | B |
| X | X | B | X | B | B |
| B | B | O | X | B | B |
| B | B | B | B | B | B |
참가자는 최소한의 시간으로 클리어하는 것이 목표다. 현재 예시에서는 참가자가 최적의 경로 (3, 5) → (3, 6) → (2, 6) → (1, 6) → (1, 5) → (1, 4) → (1, 3) → (1, 2)로 이동했을 때, 7초의 시간으로 클리어할 수 있다.
단, 참가자는 두 가지 기술 중 하나를 사전에 사용할 수 있다. 사전 사용 이후에 실질적으로 터치 미션이 진행되는 것이다. 두 가지 기술에 대한 구체적인 설명은 다음과 같다.
① 특정 타겟 제거: 원하는 타겟 지점을 하나 선택하여 없앨 수 있다. ② 벽 없애기: 벽을 하나 없앨 수 있다. 즉, 하나의 벽 X를 B로 바꾸는 것이다.
다시 말해, 참가자는 터치 미션을 진행하기 전에 둘 중 하나의 기술을 사용하여 결과적으로 터치 미션을 클리어하기 위한 시간을 줄일 수 있다. 우선 아래와 같이 "② 벽 없애기" 기술을 사용하여 하나의 벽을 없애는 경우를 고려해 보자. 없어진 벽의 위치에 대해서는 음영 처리를 했다. 이 경우 답이 5로 줄어드는 것을 확인할 수 있다. 본 예시에서 (2, 5) 위치에 있는 벽이 아닌 다른 위치에 있는 벽을 제거하더라도 가장 먼 지점인 (1, 2)까지의 거리가 5보다 작아지지 않는다.
| B | O | B | B | B | B |
|---|---|---|---|---|---|
| X | X | X | X | B | B |
| B | B | O | B | P | B |
| X | X | B | X | B | B |
| B | B | O | X | B | B |
| B | B | B | B | B | B |
혹은 아래와 같이 "① 특정 타겟 제거" 기술을 사용하여 (5, 3)에 존재하는 타겟 지점을 제거한다고 해보자. 이후에 터치 미션을 시작하면, 가장 먼 타겟 지점까지의 거리는 (1, 2)까지의 거리로 7이다. 따라서, 클리어를 위해 7초만큼의 시간이 소요된다.
| B | O | B | B | B | B |
|---|---|---|---|---|---|
| X | X | X | X | X | B |
| B | B | O | B | P | B |
| X | X | B | X | B | B |
| B | B | B | X | B | B |
| B | B | B | B | B | B |
반면에 아래와 같이 "① 특정 타겟 제거" 기술을 사용하여 (1, 2)에 존재하는 타겟 지점을 제거한다고 해보자. 이후에 터치 미션을 시작하면, 가장 먼 타겟 지점까지의 거리는 (5, 3)까지의 거리로 4이다. 따라서, 클리어를 위해 4초만큼의 시간이 소요된다.
| B | B | B | B | B | B |
|---|---|---|---|---|---|
| X | X | X | X | X | B |
| B | B | O | B | P | B |
| X | X | B | X | B | B |
| B | B | O | X | B | B |
| B | B | B | B | B | B |
따라서 본 예시에서 최종적인 답은 4이다.
입출력 예시
예시 1
입력
6, [["B", "O", "B", "B", "B", "B"], ["X", "X", "X", "X", "X", "B"], ["B", "B", "O", "B", "P", "B"], ["X", "X", "B", "X", "B", "B"], ["B", "B", "O", "X", "B", "B"], ["B", "B", "B", "B", "B", "B"]]
출력
4
예시 2
입력
6, [["P", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "O"], ["B", "B", "X", "X", "O", "O"]]
출력
-1
예시 3
입력
6, [["P", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "O"], ["B", "B", "X", "B", "O", "O"]]
출력
11
입력 조건
가장 먼저 보드의 크기 N이 자연수로 주어진다. N은 4 이상 40 이하의 자연수다.
이후에 N×N 크기의 보드의 정보가 담긴 배열 board가 주어진다. 참가자가 위치한 공간 "P"는 1개만 존재하며, 타겟 지점 "O"의 수는 최소 2개 이상 존재한다.
출력 조건
참가자가 두 가지 기술 중 하나를 사전에 사용할 수 있는 상황에서, 결과적으로 터치 미션을 클리어하는 최소 시간을 반환한다. 어떻게 하더라도 도달할 수 있는 타겟 지점이 없어 클리어할 수 없는 경우에는 -1을 반환한다.
요구사항
- solution(N, board) 함수를 만들고 답을 반환해야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 20개이고, 그 가운데 6개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 20개를 전부 통과해야 해결입니다.
예시
공개 케이스 6개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 20개를 전부 통과해야 해결입니다.
6, [["B", "O", "B", "B", "B", "B"], ["X", "X", "X", "X", "X", "B"], ["B", "B", "O", "B", "P", "B"], ["X", "X", "B", "X", "B", "B"], ["B", "B", "O", "X", "B", "B"], ["B", "B", "B", "B", "B", "B"]]
4
6, [["P", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "O"], ["B", "B", "X", "X", "O", "O"]]
-1
6, [["P", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "X"], ["B", "B", "X", "X", "X", "O"], ["B", "B", "X", "B", "O", "O"]]
11
35, [["B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "O", "B", "X", "X", "B", "B", "B", "B", "B", "O", "X", "B", "B"], ["B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B", "X", "X", "B", "X", "B", "B", "B", "X", "B", "B"], ["B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B", "O", "B", "B", "B"], ["B", "B", "B", "B", "X", "B", "X", "B", "X", "B", "B", "B", "B", "B", "O", "B", "X", "B", "B", "B", "X", "B", "B", "B", "X", "B", "X", "X", "O", "B", "B", "B", "B", "O", "B"], ["B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B", "X", "B", "B", "O", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "X", "B", "B", "B", "O"], ["B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "O", "O", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B ... 여기까지만 보여 드립니다 (전체 6,199자)
36
22, [["B", "B", "O", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "O", "B", "B", "X", "B"], ["B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "O", "X", "B", "X", "B", "B", "B", "O", "B"], ["B", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B"], ["B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "O", "X", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "X", "X", "O", "B", "B", "B", "X", "B", "X", "B", "B", "X", "B", "B", "X", "B", "B", "O", "O"], ["B", "B", "B", "B", "B", "O", "B", "B", "B", "B", "B", "B", "B", "B", "O", "O", "B", "O", "X", "B", "B", "B"], ["B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B"], ["O", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B"], ["X", "B", "B", "B", "B", "X", "B", "O", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "X", "B", "B", "X"], ["B", "X", "O", "B", "B", "B", "O", "X", "B", "B", "B", "O", "B", "B", "B", ... 여기까지만 보여 드립니다 (전체 2,468자)
23
22, [["B", "B", "B", "B", "X", "X", "X", "B", "B", "B", "X", "B", "X", "B", "B", "B", "B", "O", "X", "B", "B", "B"], ["O", "B", "B", "B", "B", "X", "B", "B", "B", "B", "O", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "X"], ["X", "B", "B", "B", "X", "O", "B", "B", "B", "B", "B", "O", "O", "B", "B", "X", "B", "B", "B", "B", "B", "B"], ["B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "O", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "O", "B", "B", "B", "B", "B", "B", "B", "B", "B"], ["X", "B", "X", "B", "B", "O", "B", "B", "B", "X", "B", "B", "O", "B", "X", "B", "X", "B", "B", "B", "B", "X"], ["B", "B", "B", "O", "B", "B", "B", "O", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "X", "B", "B", "X", "X", "X", "B", "B", "B", "B", "B", "B", "O", "B", "X", "B", "B", "B"], ["X", "B", "B", "B", "B", "B", "X", "X", "X", "B", "B", "B", "B", "O", "B", "B", "X", "B", "B", "B", "X", "B"], ["B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B"], ["B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", ... 여기까지만 보여 드립니다 (전체 2,468자)
27
참고 사항
풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.
원본에서 모의고사 2회 3번입니다.
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 6개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.