문제
건우는 공간 이동 능력 마술사, 즉 점퍼이다.
건우의 목적은 r*c의 직사각형 모양으로 생긴 정올 시티의 몇 군데를 돌아다니면서 맛있는 짜장면을 빠르게 배달해 주는 것이다.
짜장면 집은 정올 시티 밖에 있다.
건우는 처음 순간이동을 할 때는 마력을 쓰지 않는다. 그리고, 다음 순간이동부터는 다음과 같은 규칙에 따라 마력을 사용한다.
- 새로 옮겨가고자 하는 좌표를 (x1, y1)라고 할 때, 여태까지 순간이동 했던(방문했던)
모든 (x,y)좌표를 고려해서 max(|x-x1|, |y-y1|)의 최댓값 만큼 사용한다.
예를 들어, 다음과 같은 경우를 보자.
가로 3, 세로 4의 정올 시티에서 1이라고 써 있는 곳에 짜장면을 배달해 줘야 할 경우를 살펴보자.
1 0 0 0
1 0 0 0
0 0 1 0
(3,3)로 먼저 순간이동한 후, (1,1)로 갈 때는 2의 마력이 든다. 다시 (2,1) 로 갈 때에는 (1,1)과 (3,3)과의 max(|x-x1|,|y-y1|)값을 모두 고려해서 2의 마력이 들어 총 4의 마력이 든다. 그러나 (1,1) -> (2,1) -> (3,3) 순으로 이동하면 3의 마력만으로 배달 할 수 있다.
건우가 배달이 끝난 후 마력을 채우는 데는 많은 시간이 들기 때문에, 건우는 순간이동에 필요한 마력을 최소화 시키려고 한다. 건우의 짜장면 배달에 필요한 최소 마력을 구하는 프로그램을 작성하라.
입력
첫 줄에 r과c(1 <= r,c <= 50)이 들어오며, 이는 정올 시티의 크기이다.
다음 r줄의 c칸에 걸쳐서 정올 시티의 각 좌표별 상태인 정수가 들어온다. 정수는 0과 1만 입력되며, 1은 짜장면을 배달해 줘야하는 좌표이고 0은 그렇지 않은 곳이다.
출력
건우의 배달에 필요한 최소 마력을 출력한다.
예제 #1
3 4
1 0 0 0
1 0 0 0
0 0 1 0
3
예제 #2
3 4
1 1 0 1
1 0 0 0
1 1 0 1
12
출처
Hackerrank, Hard Problems.
로그인해야 코드를 작성할 수 있어요.