로그인가입
문제 목록 / A012

늑대와 닭

300점케이스 20출제 dongbinna
10월 30일에 올라온 문제입니다.
토론제출 내역

문제

N×N 크기의 맵에 K마리의 늑대와 K마리의 닭이 있다. 초기에 각 칸은 비어있거나, 벽이 존재하거나, 늑대가 한 마리 존재하거나, 혹은 닭 한 마리가 존재한다. 이때, 각 늑대에게 한 마리씩의 닭을 배정하여 잡도록 하려고 한다.

닭은 초기에 주어진 위치에 가만히 있으며, 각 늑대는 1초마다 상, 하, 좌, 우의 위치로 이동할 수 있다. 늑대는 벽이 위치한 공간으로는 이동할 수 없으며, 이동하는 과정에서는 늑대 혹은 닭을 지나칠 수 있다. 예를 들어 이동하는 과정에서 한 칸에 여러 마리의 늑대가 존재할 수 있다.

한 마리의 늑대가 자신에게 배정된 닭의 위치에 도달하면 닭은 사라지며, 늑대가 해당 위치를 차지하게 된다. 각 늑대를 한 마리의 닭에 적절히 배정하여 모든 늑대가 자신에게 배정된 닭을 잡는 데까지 걸리는 시간을 최소화하는 프로그램을 작성하여라. 자신에게 배정된 닭을 영원히 잡을 수 없는 늑대가 한 마리라도 존재하는 경우는 "무한"의 시간이 걸린다고 가정한다.

예를 들어 N=5이고, K=3인 상황을 가정하자. 늑대가 존재하는 위치로 "W"로 표시되고, 닭이 존재하는 위치는 "C"로 표시된다. 또한 벽이 존재하는 위치는 "X"로 표시되고, 빈 공간은 "B"로 표시된다.

BWBCB
XXXXX
BCCBB
BBXBB
WBXWB

각 위치를 (행, 열)의 형태로 나타낸다고 가정하자. 행과 열의 인덱스가 0부터 시작한다고 하면, 현재 예시에서는 (0, 1)에 위치한 늑대가 (0, 3)에 위치한 닭을 잡고, (4, 0)에 위치한 늑대가 (2, 1)에 위치한 닭을 잡고, (4, 3)에 위치한 늑대가 (2, 2)에 위치한 닭을 잡는 것이 최적이다. 결과적으로 현재 예시에서는 모든 늑대가 자신에게 배정된 닭을 잡는 데까지 걸리는 시간의 최솟값은 3초다.

입출력 예시

예시 1

입력

5, 3, [["B", "W", "B", "C", "B"], ["X", "X", "X", "X", "X"], ["B", "C", "C", "B", "B"], ["B", "B", "X", "B", "B"], ["W", "B", "X", "W", "B"]]

출력

3

예시 2

입력

5, 3, [["C", "X", "B", "W", "B"], ["X", "X", "X", "X", "B"], ["B", "C", "C", "B", "B"], ["B", "B", "X", "B", "B"], ["W", "B", "X", "W", "B"]]

출력

0

예시 3

입력

5, 4, [["C", "C", "C", "C", "B"], ["X", "X", "X", "X", "B"], ["B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["B", "W", "W", "W", "W"]]

출력

8

예시 4

입력

5, 6, [["C", "C", "C", "C", "B"], ["X", "B", "X", "X", "W"], ["B", "B", "B", "W", "B"], ["B", "C", "B", "B", "C"], ["B", "W", "W", "W", "W"]]

출력

5

입력 조건

  • 가장 먼저 전체 맵의 크기 N이 주어진다. N은 5 이상 200 이하의 자연수다.

  • 이어서 늑대와 닭의 수 K가 주어진다. K는 1 이상 9 이하의 자연수다.

  • 이어서 N×N 크기의 전체 맵의 정보가 담긴 2차원 배열 arr가 주어진다. 늑대가 존재하는 위치로 "W"로 표시되고, 닭이 존재하는 위치는 "C"로 표시된다. 또한 벽이 존재하는 위치는 "X"로 표시되고, 빈 공간은 "B"로 표시된다.

출력 조건

  • 각 늑대마다 한 마리의 닭을 적절히 배정하여, 모든 늑대가 자신에게 배정된 닭을 잡는 데까지 걸리는 시간을 최소화했을 때의 걸리는 시간을 반환한다. 단, 늑대를 어떻게 배정하더라도 잡을 수 없는 닭이 존재하는 경우(모든 늑대가 자신에게 배정된 닭을 잡는 데까지 걸리는 시간의 최솟값이 "무한"인 경우) 0을 반환한다.

요구사항

  • solution(N, K, arr) 함수를 만들고 답을 반환해야 합니다
  • 쓸 수 있는 말은 파이썬, 자바스크립트입니다
  • 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
  • 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
  • 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
  • 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
  • 케이스는 20개이고, 그 가운데 7개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
  • 케이스 20개를 전부 통과해야 해결입니다.
문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

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

입력
기대 출력
5, 3, [["B", "W", "B", "C", "B"], ["X", "X", "X", "X", "X"], ["B", "C", "C", "B", "B"], ["B", "B", "X", "B", "B"], ["W", "B", "X", "W", "B"]]

3
5, 3, [["C", "X", "B", "W", "B"], ["X", "X", "X", "X", "B"], ["B", "C", "C", "B", "B"], ["B", "B", "X", "B", "B"], ["W", "B", "X", "W", "B"]]

0
5, 4, [["C", "C", "C", "C", "B"], ["X", "X", "X", "X", "B"], ["B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B"], ["B", "W", "W", "W", "W"]]

8
5, 6, [["C", "C", "C", "C", "B"], ["X", "B", "X", "X", "W"], ["B", "B", "B", "W", "B"], ["B", "C", "B", "B", "C"], ["B", "W", "W", "W", "W"]]

5
75, 9, [["B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "X", "X", "B", "X", "X", "X", "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", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "X", "B", "X", "B", "B", "X", "X", "X", "X", "B"], ["B", "X", "B", "X", "X", "B", "B", "X", "X", "B", "B", "B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "B", "X", "B", "X", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X", "B", "X", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "X", "B", "B", "X", "X", "B", "X", "B", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B"], ["B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", 

... 여기까지만 보여 드립니다 (전체 28,282자)
40
30, 7, [["X", "B", "B", "B", "X", "X", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "B", "B", "B", "B", "B", "B"], ["B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "C", "B", "B", "B", "B", "X", "B", "B", "X", "B", "X"], ["B", "X", "B", "B", "B", "X", "B", "X", "B", "B", "B", "X", "X", "B", "X", "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", "X", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B"], ["B", "X", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B"], ["X", "B", "X", "B", "B", "X", "B", "B", "X", "B", "X", "X", "B", "B", "X", "B", "B", "X", "X", "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", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "X", "X"], ["B", "B", "B", "B", "W", "X", "X", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "C", "B", "B", "B", "B", "B", "B", "B", "B

... 여기까지만 보여 드립니다 (전체 4,567자)
19
93, 4, [["B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "X", "X", "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", "B", "B", "B", "B", "B", "X", "X", "X", "B", "B", "X", "B", "X", "X", "X", "B", "B", "X", "B", "X", "B", "X", "X", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "X"], ["X", "B", "B", "B", "X", "B", "X", "B", "B", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "B", "X", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "B", "X", "B", "X", "B", "X", "B", "X", "B", "B", "X", "B", "B", "B", "B", "B", "X", "X", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "B", "X", "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", "X", "B", "B", "B", "B", "X", "B", "X", "B", "B", "B", "X", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "X", "B", "B", "B", "B", "B", "B", "B", "B", "X", "X

... 여기까지만 보여 드립니다 (전체 43,438자)
90

참고 사항

풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.

원본에서 모의고사 4회 3번입니다.

풀이

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

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

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

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

이 문제를 푼 사람

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