드론(drone) > 문제은행



문제은행

3432 : 드론(drone)

제한시간: 3Sec    메모리제한: 1024mb
해결횟수: 3회    시도횟수: 28회   



전후좌우 네 방향으로만 움직일 수 있는 드론이 있다. 이 드론은 1초 동안 1m 를 움직일 수 있고, 

고도는 항상 1m를 유지한다. 드론의 크기는 1m​2의 정사각형에 겨우 들어갈 정도이다.

 

드론에는 정수 인식 센서가 달려있어서, 드론의 아래에 정수가 위치하면 이를 외부 전광판에 표시한다. 

다만 이 센서는 붉은색 테두리 안에 있는 정수만 인식할 수 있다.

 

민수는 드론이 이동할 수 있는 미로를 만들었다. 

미로의 바닥은 1m​2​ 크기의 정사각형 타일이 N×N격자로 배치된 정사각형 형태이다. 

이 미로는 입구와 출구만 제외하곤 높이 2m​인 벽으로 둘러 쌓여있다. 

입구는 항상 1행 1열의 왼쪽 부분이고, 출구는 항상 NN열의 오른쪽 부분이다. 

그리고 미로 내부에는 한 변이 맞닿은 두 타일 사이에 폭 1m​, 높이 2m​인 벽이 있을 수 있다.

 

미로의 타일은 모두 흰색이지만, 일부 타일은 LED로 만들어져서 필요한 경우 타일 테두리를 붉은색으로 바꿀 수 있다. 

물론 다시 흰색으로도 바꿀 수 있다. 그리고 LED​ 타일에는 1부터 N2까지 정수 중 하나의 수가 적혀있다. 

미로에는 같은 수가 적힌 LED 타일이 여러 개 있을 수도 있다.

 

민수는 드론과 미로를 이용한 특별한 레이싱 게임을 고안했다. 

1부터 N2​까지의 정수로 구성된 수열 s1, s2, ..., sT가 주어지면 

전광판에 동일한 수열이 표시되도록 드론을 입구에서 출구까지 움직이면 된다. 

단, 동일한 정수가 연속된 경우는 없다고가정한다. 

또한 항상 레이싱 게임이 끝날 수 있는 수열이 주어진다고 가정한다. 

전광판에 잘못된 수열이 표시되지 않도록 s1​부터 순서대로 해당 정수가 적힌 LED타일들의 테두리를 붉은색으로 바꾸고, 

드론이 도착하여 전광판에 s1​이 표시되면 LED 타일들은 다시 흰색으로 바뀌며 

이제 s2​가 적힌 LED 타일들의 테두리가 붉은색으로 바뀐다.​ 

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563680 

 

예를 들어, <그림1>은 4×4개의 타일로 구성된 미로를 나타낸다. 

미로의 입구는 들어가는 화살표로 표시된 곳으로 드론이 입구 바로 밖에 대기하고 있다. 

출구는 나가는 화살표로 표시된 곳이다. 미로에는 3개의 LED 타일이 있으며, 각각 1, 9, 15를 나타낸다.​ 

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563681
 

 

수열 1, 15, 9, 15가 주어진 경우 우선 정수 1이 적힌 2행 2열 타일에 붉은색 테두리가 생기고 

미로 밖 전광판에는 아직 아무것도 표시되진 않았다(<그림 2> 왼쪽).

드론을 움직여 1이 적힌 LED 타일에 도착하면 전광판에 1이 표시되고(<그림 2>가운데), 

이제 수열의 다음 수인 15에 해당하는 1행 4열 타일에 붉은색 테두리가 생긴다(<그림 2> 오른쪽).​ 

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563681
 

 

이후 드론을 움직여 15, 9, 15까지 전광판에 표시한 후 출구로 나가면 레이싱 게임

이 끝난다. 레이싱 게임 동안 드론이 움직이는 방법은 여러 가지가 있을 수 있다.

<그림 3>은 그 중 한 가지 이동 경로를 나타낸다.

 

여러분은 레이싱 게임에 소요되는 시간의 최솟값을 계산하여 출력한다. 

위 예의 최솟값은 22로 <그림 3>은 그때의 이동 경로이다.​ 

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563681
 


표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 미로의 크기를 나타내는 정수 N이 주어진다(1 ≤ N ≤ 500). 
이어지는 N줄 각각엔 N개의 정수가 주어지는데 각 정수는 해당 타일의 네 변에 존재하는 벽의 위치를 
<그림 4>에서 보인 것처럼 2진수 방식으로 표현한 것으로 0부터 15까지의 값을 가진다.


다음 줄에는 LED 타일의 개수를 나타내는 정수  M( 1 ≤ M ≤min{N2, 100}) 이 주어지고, 
이어지는 M개 줄 각각에 LED 타일의 위치 xiyi(1 ≤ i ≤ M)과 
타일에 적힌 정수 ci가 차례대로 주어진다( 1 ≤ xi, yi ≤N, 1 ≤ ci ≤ N2 ).
다음 줄에는 수열의 크기를 나타내는 정수 T(T ≤ T ≤ 1000)가 주어지고, 
이어지는 줄에 T개의 정수 sj(1 ≤ j ≤ T)가 주어진다(1 ≤ sj ≤ N2). 
이때 모든 sj에 대해 sj = ci이면서 해당 LED 타일
위치에 드론이 도달할 수 있는 ci가 존재한다. 
또한 모든  sk(1 ≤ k < T)에 대해  sk ≠sk+1 이다.


표준 출력으로 레이싱 게임에 소요되는 시간의 최솟값을 정수로 출력한다.

[부분문제의 제약 조건]
부분문제 1: 전체 점수 100점 중 3점에 해당하며  N ≤ 4, M ≤ 4, T ≤ 4 이다.
부분문제 2: 전체 점수 100점 중 20점에 해당하며  N ≤ 50, M ≤ 10, T ≤ 100 이다.
부분문제 3: 전체 점수 100점 중 5점에 해당하며 미로 내부에 벽이 없고, 
            LED 타일에 적힌 수는 모두 서로 다르다 (i≠j 이면  ci ≠ cj (1 ≤ i, j ≤ M)).
부분문제 4: 전체 점수 100점 중 19점에 해당하며 LED 타일에 적힌 수는 모두 서로 다르다(i≠j 이면  ci ≠ cj (1 ≤ i, j ≤ M)).
부분문제 5: 전체 점수 100점 중 53점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
3
5 1 3
15 10 10
13 4 4
2
1 2 5
3 2 7
2
5 7
[Copy]
6


[Copy]
4
5 1 5 3
9 6 9 2
8 1 6 10
14 12 7 12
3
1 4 15
2 2 1
4 3 9
4
1 15 9 15
[Copy]
22


[Copy]
4
5 1 5 3
9 6 9 2
8 1 6 10
14 12 7 12
5
1 4 15
2 2 1
3 3 1
3 4 13
4 3 3
5
1 15 1 3 13
[Copy]
20






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.