전장속으로 - 최종

문제

---

비행기에서 뛰어내려 특정 좌표에 도착해 전투를 시작한다. 현재 레벨에 따라 잡을 수 있는 적의 레벨이 다르다. 예를 들어, 현재 레벨이 5일 경우 5 보다 작은 숫자인 레벨 1, 2, 3, 4 에 해당하는 적을 잡을 수 있다. 현재 레벨과 동일한 수의 적을 잡을 경우 레벨업을 한다. 이때 증가한 레벨은 1이다. 만약 현재 레벨이 2라면 2명의 적을 잡아야한다. 2명을 잡았을 경우 레벨업하여 레벨 3이 된다.

[그림 1]

비행기에서 내려 땅에 도착했을 때의 레벨은 2이며, 도착한 순간부터 현재 위치에서 가장 가깝고 사살할 수 있는 적부터 찾아 나선다. 사살할 수 있는 적이 많다면 가장 위쪽을 우선으로 타겟을 잡는다. 만약 위쪽에서도 적이 많다면 그 중에서도 가장 왼쪽에 있는 적으로 아동한다. 좌표 이동을 한 칸하는데에 1분이 소요되며, 현재 좌표의 인접한 4방향(상하좌우)으로만 이동이 가능하다. 만약 이동하고자하는 위치에 현재 레벨보다 높은 레벨의 적이 있다면 이동할 수 없다. 같은 레벨의 적이 있는 경우 지나갈 수는 있지만 사살할 수는 없다. 낮은 레벨의 적이 있다면 해당 위치에 도착함과 동시에 적을 섬멸한다. 적을 섬멸하는데에 소요되는 시간은 따로 없다.

전장의 정보가 주어졌을때, 사살할 수 있는 적을 모두 섬멸하는데에 걸리는 시간은 몇 분인가? 위 그림의 예에서 이어서 상황을 그려본다면 다음과 같은 절차를 통해 적을 섬멸한다. 총 걸리는 시간은 15분이다.

[그림 2]

[그림 3]

[그림 4]

 

입력

---

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄부터 T개의 테스트 케이스에 대한 정보가 주어진다. 각각의 테스트 케이스의 첫 번째 줄에 전장의 크기 N이 주어진다. 두 번째 줄부터 N개의 줄에 걸쳐 전장의 정보가 주어진다. 각 숫자는 0부터 9까지의 자연수이며, 0은 아무것도 없음, 1부터 8까지의 수는 적의 레벨을 뜻한다. 9의 경우 비행기에서 내려 도착한 위치를 뜻한다. (2 ≤ N ≤ 20)

 

출력

---

각 테스트 케이스에 대해 최대한 적을 섬멸하는데에 걸리는 시간을 출력한다. 각 테스트 케이스의 출력 양식은 "#t r"이다. t는 테스트 케이스의 번호이며, 1부터 시작한다. r은 문제에 대한 결과값을 뜻한다.

 

예제 입력

5
5
0 1 0 1 0 
0 0 0 0 2 
0 2 0 2 0 
0 3 9 0 0 
1 3 0 0 0 
4
0 4 5 0 
1 1 9 1 
4 5 2 5 
6 0 3 6
4
5 4 3 1 
5 1 2 7 
3 2 3 0 
0 0 9 1 
5
3 2 5 0 9 
0 3 0 0 2 
2 0 0 2 5 
7 0 0 1 3 
2 2 0 1 7 
7
1 1 0 5 9 1 3 
5 2 3 1 6 2 2 
7 0 5 1 1 4 1 
4 0 0 3 1 2 1 
0 0 1 6 7 0 1 
3 8 1 2 6 1 8 
7 6 1 0 5 0 8 

예제 출력

#1 15
#2 7
#3 17
#4 27
#5 70

 

풀이

1) 공격수의 x좌표, y좌표 확인하기

2) 공격수는 최소한의 거리에 있는 적군을 잡기 위해서 맵에 적군이 없을때까지 반복한다

 2-1) BFS를 통해서 방문 가능성 체크 맵(현재 레벨보다 작거나 같은 곳은 방문 가능 True), 떨어진 거리 맵 생성 

 2-2) 맵에서 공격수의 레벨보다 작거나 같은데 거리가 최소인 적 위치 찾기

 2-2) 적군을 다 잡았을 경우 반복문 종료 조건

 2-3) 소요시간 누적, level_map에서 잡은 적군 제거, 적 잡은 수 누적

 2-4) 공격수의 좌표 갱신

 2-5) 현재 레벨만큼 적군의 수 잡았을 경우 레벨 업

 

- 8개 테스트 케이스 중에서 2개가 런타임 에러 발생하여 코드 수정이 필요하다.

from collections import deque

#공격수 좌표를 시작점으로 갈수있는 곳(레벨보다 같거나 낮은 곳), 갈수 없는 곳(레벨보다 큰 곳) 체크
#공격수 좌표를 시작점으로 거리 구하기
def do_BFS(row, attacker_level, level_list, attacker_x, attacker_y) :
  visite_list = [[False] * row for _ in range(row)]
  distance_list = [[0] * row for _ in range(row)]
  
  dx = [-1, 0, 1, 0]                              #위 0, 오른 1, 아래쪽 2, 왼쪽 3
  dy = [0, 1, 0, -1]
  
  dq = deque()                                    #BFS를 위한 큐 생성
  
  dq.append((attacker_x, attacker_y))             #1. 큐에 시작점 추가
  visite_list[attacker_x][attacker_y] = True      #2. 큐에 넣은 시작점은 방문처리
  
  #위 오른쪽 아래 왼쪽 움직이는 BFS 시작
  while dq :                            #3. 큐가 텅 빌때까지 방문
    now_idx = dq.popleft()              #큐에는 [(x, y)] 좌표 들어감
    
    for i in range(4) :                 #위 0, 오른 1, 아래쪽 2, 왼쪽 3 방향 반복하면서 큐에 4방향 순회
      next_x = now_idx[0] + dx[i]       #큐에 들어간 좌표 중 다음 x좌표[0]
      next_y = now_idx[1] + dy[i]       #큐에 들어간 좌표 중 다음 y좌표[1]  
  
      if 0 <= next_x <= (row-1) and 0 <= next_y <= (row-1) :  #테두리 이상 벗어나지 않는 조건
        if visite_list[next_x][next_y] is not True:           #이미 방문한 곳은 재방문 하지않음
          if level_list[next_x][next_y] == 0 or level_list[next_x][next_y] <= attacker_level :      #방문할 곳이 0이거나 레벨이 작거나 같은 경우 방문 가능
            visite_list[next_x][next_y] = True                #방문한 곳은 재방문 방지를 위해 True 처리
            dq.append((next_x, next_y))
            distance_list[next_x][next_y] = distance_list[now_idx[0]][now_idx[1]] + 1               #공격자가 못가는 경우를 피해서 가는 최단 거리
  
  return visite_list, distance_list     #방문 가능성 맵, 거리 맵 반환

#최소 거리 구하는 함수
def find_min_distance(row, attacker_level, level_list, visite_list, distance_list) :
  min_distance = 99999999
  min_x = -1
  min_y = -1
  
  for x in range(row) :
    for y in range(row) :
      #방문 가능하며, 공격자의 레벨보다 낮고, 0이 아니며, 거리가 작은 것을 구해라
      if visite_list[x][y] is True and level_list[x][y] < attacker_level and level_list[x][y] != 0 and distance_list[x][y] < min_distance :
        min_distance = distance_list[x][y]
        min_x = x
        min_y = y

  return min_distance, min_x, min_y       #최소좌표의 값, x좌표, y좌표 갱신

#메인함수 시작
if __name__ == "__main__":
  test_case = int(input())
  
  for i in range(test_case) :                       #테스트 케이스 수만큼 반복 시작
    row = int(input())                              #n*n 행렬 너비
  
    data = []
    level_map = []                                  #기본 레벨 맵
    
    #1) 공격수의 x좌표, y좌표 확인하기
    for x in range(row) :                           #맵 데이터 입력 받아서 맵 생성
      data = list(map(int, input().split()))
      level_map.append(data)
    
      for y in range(len(data)) :                   #입력 받으면서 최초의 공격수 9 찾기
        if data[y] == 9 :
          attacker_x = x
          attacker_y = y
          level_map[attacker_x][attacker_y] = 0     #공격수 좌표는 찾았으므로 그냥 0으로 만들어줌
    
    attacker_level = 2                              #공격수의 최초 레벨은 2
    
    kill_count = 0                                  #공격수가 적을 잡은 횟수
    result_time = 0
    
    #2) 공격수는 최소한의 거리에 있는 적군을 잡기 위해서 맵에 적군이 없을때까지 반복한다
    while True :
      #2-1) BFS를 통해서 방문 가능성 체크 맵(현재 레벨보다 작거나 같은 곳은 방문 가능 True), 떨어진 거리 맵 생성 
      visite_map, distance_map = do_BFS(row, attacker_level, level_map, attacker_x, attacker_y)
      
      #2-2) 맵에서 공격수의 레벨보다 작거나 같은데 거리가 최소인 적 위치 찾기
      min_distance, min_x, min_y = find_min_distance(row, attacker_level, level_map, visite_map, distance_map)
      
      #2-2) 적군을 다 잡았을 경우 반복문 종료 조건
      if min_distance == 99999999 :               #최소값이 99999999인 경우 잡을 것 없음 while문 탈주
        break
      
      #2-3) 소요시간 누적, level_map에서 잡은 적군 제거, 적 잡은 수 누적
      result_time += distance_map[min_x][min_y]   #최소값 좌표까지 걸리는 시간 계산
      level_map[min_x][min_y] = 0                 #최소값 좌표에 있는 적을 잡은 자리는 0으로 만들어줌
      kill_count += 1                             #적을 잡은 개수 카운트
      
      #2-4) 공격수의 좌표 갱신
      attacker_x, attacker_y = min_x, min_y       #적을 잡고 잡은 후 공격수 좌표 갱신
      
      #2-5) 현재 레벨만큼 적군의 수 잡았을 경우 레벨 업
      if kill_count == attacker_level :           #공격수가 적을 잡은 개수와 같으면 레벨업
        attacker_level += 1
        kill_count = 0
        #print("level_Up~~~~~", attacker_level)
      
      #print(level_map)
      #print("result_time", result_time)
      #print("attacker_x,y :", attacker_x, attacker_y)
    
    print("#", end="")
    print(i+1, result_time)