전장속으로 - E

문제

---

비행기에서 뛰어내려 특정 좌표에 도착해 전투를 시작한다. 낙하한 위치에서 가장 가까운 적을 우선으로 섬멸한다. 적을 모두 사살하면 게임이 종료된다. 게임이 종료되기까지 걸리는 시간을 알고 싶다.

이동은 상하좌우로만 할 수 있으며, 대각선으로는 이동할 수 없다. 이동하는데에 소요되는 시간은 격자판 기준 1칸 이동시 1분이 소요된다. 만약 거리가 같은 적이 2명 이상일 경우 y 좌표가 작은 적에게 우선 이동한다. 거리가 같고, y 좌표가 동일한 적이 2명 이상일 경우 x 좌표가 작은 적을 향해 이동한다. 적의 위치에 도착하자마자 적은 사살되며, 적을 사살하는데에 걸리는 시간은 없다고 본다.

그림의 왼쪽과 같이 적이 주어지고, (4, 3)의 위치에 낙하했다고 생각해보자. 그렇다면 오른쪽과 같이 각 적에 대한 이동 소요시간을 알 수 있다. 가장 가까운 위치에 존재하는 (4, 2)에 존재하는 적에게 이동한다.

(4, 2)로 이동을 한 뒤 다시 각 적에 대한 이동 소요시간을 계산하면 위의 오른쪽 그림과 동일하다. 가장 가까운 적 중에서 위에 있는 적에게 가야되므로 (3, 2)로 이동한다. 위 예시에서 적을 모두 섬멸하는데에 걸리는 시간은 15 이다.

위와 같은 절차를 적이 모두 없어질때까지 반복한다고 했을때, 주어진 전장의 정보에서 적을 모두 없애기까지 이동한 거리를 구해보자.

입력

---

첫 번째 줄에 전장의 크기 N이 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 전장의 정보가 주어진다. 각 줄은 N개의 숫자로 이루어져 있으며, 각 숫자는 0, 1, 9 중에 하나이다. 0은 아무것도 없음, 1은 적, 9는 낙하 지점을 의미한다. 9는 하나만 주어진다.

왼쪽 최상단의 좌표는 (1, 1)이다.

(2 ≤ N ≤ 20)

출력

---

주어진 전장의 정보에서 적을 모두 없애기까지 이동한 거리를 출력한다.

입력의 예 1

5
0 1 0 1 0 
0 0 0 0 1 
0 1 0 1 0 
0 1 9 0 0 
1 1 0 0 0

출력의 예 1

15

입력의 예 2

7
1 1 0 1 9 1 1 
1 1 1 1 1 1 1 
1 0 1 1 1 1 1 
1 0 0 1 1 1 1 
0 0 1 1 1 0 1 
1 1 1 1 1 1 1 
1 1 1 0 1 0 1

출력의 예 2

46

 

풀이

 - map_data가 1인 경우에 공격자로부터 x좌표, y좌표 거리값 구하기 

 - 최소값인 경우 방문 및 0으로 변경

 - 구한 거리값이 모두 방문한 경우 중단

if __name__ == "__main__":
  row = int(input())            #n*n 행렬 너비
  data = []
  map_data = []

  attacker_x = -1                       #공격수 x좌표, y좌표 초기 값은 -1
  attacker_y = -1
  
  distance_list = [[0] * row for _ in range(row)]
  result = 0
  
  for x in range(row) :                 #맵 데이터 입력 받아서 맵 생성
    data = list(map(int, input().split()))
    map_data.append(data)
    
    for y in range(len(data)) :         #입력 받으면서 최초의 공격수 9 찾기
      if data[y] == 9 :
        attacker_x = x
        attacker_y = y
  
  while True :
    for x in range(row) :
      for y in range(row) :
        if map_data[x][y] != 0 and map_data[x][y] != 9 :                    #map_data[x][y] 값이 1인경우 거리값 구하기(0과 9가 아닌경우)
          distance_list[x][y] = abs(attacker_x - x) + abs(attacker_y - y)   #공격수로부터의 거리 차이 찾기
        else :
          distance_list[x][y] = 99999999                                    #0이거나, 9인곳은 거리 차이 값을 99999999로 변경
    #print(distance_list)
    min_distance = 99999999
    min_x = -1
    min_y = -1
    
    for x in range(row) :
      for y in range(row) :
        if distance_list[x][y] < min_distance :         #거리가 최소값인 경우 찾기
          min_distance = distance_list[x][y]            #최소값 갱신
          min_x = x                                     #최소값 x좌표 갱신
          min_y = y                                     #최소값 y좌표 갱신
    
    if min_distance == 99999999 :    #최소값 찾아서 0으로 변경 후 else distance_list[x][y] = 99999999로 변경해서 전체가 전부 
      break                          #99999999여서 최소값이 99999999 인경우 반복문 종료
    
    result += (abs(attacker_x - min_x) + abs(attacker_y - min_y))     #걸린 시간 합하기
    
    attacker_x = min_x                                  #다음 공격자 x좌표는 최소값 x좌표로 갱신
    attacker_y = min_y                                  #다음 공격자 y좌표는 최소값 y좌표로 갱신
    
    map_data[min_x][min_y] = 0                          #방문했던 곳은 0으로 변경(위에서 else distance_list[x][y] = 99999999로 변경)
  
  print(result)