두 명의 기사
문제
N×N 크기의 보드 판에 주인공 1명, 기사 2명이 존재하며, 적군은 최소한 1명 이상 존재한다. 주인공의 위치는 "H", 기사의 위치는 "K", 적군의 위치는 "E"로 표시된다. 또한 빈 공간은 "B", 벽은 "X"로 표시된다. 한 위치에 여러 명이 존재하지 않는다.
주인공은 움직일 수 없으며, 기사는 원한다면 체스 말처럼 현재 위치에서 8가지 위치 중 하나로 이동할 수 있다. 기사가 N×N 격자 위치에서 이동 가능한 8가지 방향을 그림으로 표현하면 다음과 같다.
예를 들어 (행, 열)의 형태로 각 위치를 나타낸다고 가정하자. 행과 열의 인덱스가 0부터 시작한다고 하면, (3, 3)의 위치에서 이동이 가능한 위치는 (1, 2), (1, 4), (2, 1), (2, 5), (4, 1), (4, 5), (5, 2), (5, 4)이다. 아래 그림에서 음영으로 칠한 위치들과 같다.
| ● | ● | |||||
| ● | ● | |||||
| K | ||||||
| ● | ● | |||||
| ● | ● |
위 표는 7행 7열 격자이며 기사(K)가 (3, 3)에 있다. 원본에서는 이동 가능한 8가지 위치가 음영으로만 표시되어 있어 텍스트 추출에서 셀 값이 남지 않았다. 본문에 적힌 위치 목록을 그대로 옮겨 ● 로 표시했다.
2명의 기사는 처음 놓인 위치에 가만히 있는 것도 가능하며, 각자 빈 공간 혹은 적군이 있는 위치로 최대 1회 움직일 수 있다. 단, 벽이 있는 위치로는 이동할 수 없다. 적군이 있는 위치로 이동하게 되면, 적군은 제거되고, 그 위치를 기사가 차지한다. 특정한 기사는 최대 1회 이동을 수행하면 더 이상 움직일 수 없으며, 두 기사의 이동이 모두 끝나고 나면 적군의 이동이 시작된다. 기사 및 적군의 이동 과정에서 한 위치에 여러 명이 존재할 수 없다.
각 적군은 매 초마다 현재 위치에서 상, 하, 좌, 우로 이동할 수 있다. 기사 혹은 벽이 존재하는 위치로는 이동할 수 없으며, 주인공이 위치한 곳까지 도달하면 전체 과정이 종료된다.
예를 들어 N=5인 예시를 확인해 보자. 현재 예시에서는 (1, 1) 위치에 있는 기사를 가만히 두고, (0, 1) 위치에 있는 기사를 (2, 2) 위치로 이동시켜 적군을 처리할 수 있다.
| B | K | B | B | B |
|---|---|---|---|---|
| B | K | E | E | B |
| B | B | E | X | B |
| B | B | X | X | B |
| H | B | X | B | E |
그 결과 다음과 같이 보드 판이 변경된다.
| B | B | B | B | B |
|---|---|---|---|---|
| B | K | E | E | B |
| B | B | K | X | B |
| B | B | X | X | B |
| H | B | X | B | E |
이 경우, 가장 가까운 적군이 주인공에 도달하기 위한 최소 시간은 7초이다.
결과적으로, 2명의 기사를 적절히 활용하여 가장 가까운 적군이 주인공에 도달하기 위한 시간을 최대화하는 것이 목표다. 목표에 맞게 2명의 기사를 적절히 활용했을 때, 가장 가까운 적군이 주인공에 도달하기 위한 최소 시간을 출력하는 프로그램을 작성하여라. 적군이 도달 불가능하게 만들 수 있다면 0을 출력한다. 본 문제에서는 항상 행과 열의 인덱스가 0부터 시작한다.
입출력 예시
예시 1
입력
5, [["B", "K", "B", "B", "B"], ["B", "K", "E", "E", "B"], ["B", "B", "E", "X", "B"], ["B", "B", "X", "X", "B"], ["H", "B", "X", "B", "E"]]
출력
7
예시 2
입력
5, [["E", "E", "E", "E", "E"], ["E", "E", "E", "E", "E"], ["E", "E", "E", "E", "E"], ["K", "E", "E", "E", "E"], ["H", "K", "E", "E", "E"]]
출력
0
예시 3
입력
5, [["B", "B", "B", "B", "E"], ["B", "B", "B", "B", "B"], ["K", "K", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["H", "X", "E", "B", "B"]]
출력
8
예시 4
입력
5, [["B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["K", "K", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["H", "X", "E", "B", "B"]]
출력
0
입력 조건
가장 먼저 보드 판의 크기 N이 주어진다. N은 4 이상 100 이하의 자연수다.
이어서 행과 열의 길이가 각각 N인 2차원 배열 형태의 보드 판 정보 배열 board가 주어진다. 이때 주인공의 위치는 "H", 기사의 위치는 "K", 적군의 위치는 "E"로 표시된다. 또한 빈 공간은 "B", 벽은 "X"로 표시된다. 보드 판에는 항상 주인공 1명, 기사 2명이 존재하며, 적군은 최소한 1명 이상 존재한다.
출력 조건
목표에 맞게 2명의 기사를 적절히 활용했을 때, 가장 가까운 적군이 주인공에 도달하기 위한 최소 시간을 반환한다.
요구사항
- solution(N, board) 함수를 만들고 답을 반환해야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 20개이고, 그 가운데 7개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 20개를 전부 통과해야 해결입니다.
예시
공개 케이스 7개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 20개를 전부 통과해야 해결입니다.
5, [["B", "K", "B", "B", "B"], ["B", "K", "E", "E", "B"], ["B", "B", "E", "X", "B"], ["B", "B", "X", "X", "B"], ["H", "B", "X", "B", "E"]]
7
5, [["E", "E", "E", "E", "E"], ["E", "E", "E", "E", "E"], ["E", "E", "E", "E", "E"], ["K", "E", "E", "E", "E"], ["H", "K", "E", "E", "E"]]
0
5, [["B", "B", "B", "B", "E"], ["B", "B", "B", "B", "B"], ["K", "K", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["H", "X", "E", "B", "B"]]
8
5, [["B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["K", "K", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["H", "X", "E", "B", "B"]]
0
51, [["B", "B", "B", "E", "B", "E", "X", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "E", "E", "B", "B", "X", "B", "B", "E", "B", "B", "B", "X", "B", "B", "B", "B", "B", "E", "B", "B", "E", "B", "B", "B", "B", "B", "X", "B", "B", "B"], ["B", "B", "B", "X", "X", "B", "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", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B"], ["B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "B", "X", "B", "X", "B", "B", "B", "E", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "X", "B", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "X", "B", "B", "B", "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"], ["X", "B", "X", "X", "B", "B", "B", "B", "X", "B", "B", "E", "B", "B", "X", "E", "B", "B", "B", "X", "B", "X", "X", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", " ... 여기까지만 보여 드립니다 (전체 13,111자)
4
71, [["B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "X", "B", "B", "X", "B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "E", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B"], ["B", "B", "B", "B", "X", "E", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "E", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "E", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "E", "B"], ["B", "B", "B", "B", "B", "X", "E", "E", "B", "E", "B", "X", "B", "E", "B", "E", "B", "X", "B", "X", "B", "X", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "X", "E", "B", "X", "B", "B", "B", "B", "B", "B", "X", "E", "B", "B", "B", "B", "E", "B", "B", "B", "B", "X", "B", "X", "B", "X", "B", "X", "B", "B", "B", "B"], ["B", "B", "B", "E", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B" ... 여기까지만 보여 드립니다 (전체 25,351자)
5
77, [["B", "B", "B", "B", "B", "B", "X", "B", "E", "B", "B", "B", "B", "X", "B", "B", "E", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "X", "B", "X", "B", "B", "B", "X", "X", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "B", "B", "E", "X", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "X", "B"], ["B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "X", "B", "X", "B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "E", "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", "E", "B", "B", "B", "B", "X", "E", "B", "B", "B", "X", "B", "B", "B", "X", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "E", "B", "B", "B", "E", "B", "B", "B", "B", "X", "B", "X", "B", "B", "E", "B", "X", "B"], ["X", "B", "E", "X", "B", "B", "B" ... 여기까지만 보여 드립니다 (전체 29,803자)
6
참고 사항
풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.
원본에서 모의고사 4회 2번입니다.
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 7개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.