전장속으로 - D

문제

---

비행기에서 뛰어내려 특정 좌표에 도착해 전투를 시작한다. 전투 투시경을 통해 현재 위치에서 모든 적의 위치가 보인다. 일단 전투를 시작하기 전 현재 위치에서 각각의 적까지의 거리를 구해놓을려고 한다. 거리는 현재 위치 (a, b) 와 적의 위치 (c, d) 를 알면 |a-c| + |b-d| 로 구할 수 있다.

이동은 상하좌우로만 할 수 있으며, 대각선으로는 이동할 수 없다. 또한, 자신의 레벨보다 높은 레벨의 적을 뚫고 지나갈 수 없다. 자신의 레벨과 같은 레벨의 적은 잡을 수는 없으나, 지나갈 수 있다. 만약 거리가 같은 적이 2명 이상일 경우 y 좌표가 작은 적에게 우선 이동한다. 거리가 같고, y 좌표가 동일한 적이 2명 이상일 경우 x 좌표가 작은 적을 향해 이동한다.

위와 같이 적들이 존재하는 경우를 예를 들어보자. 적 중에서 나의 레벨보다 작은 적은 (1, 2), (1, 4), (5, 1) 위치에 존재한다. 이 중에서 적까지 도달하는데에 걸리는 시간이 제일 작은 적의 위치는 (1, 2), (1, 4)이다. 이 중에서 가장 위쪽에 있으면서 가장 왼쪽에 있는 적은 (1, 2)이므로 (1, 2)로 이동한다.

전장의 정보와 낙하 지점이 주어졌을때, 낙하 지점에서 가장 가깝고, 현재 레벨보다 낮은 적의 위치를 알아보자.

입력

---

첫 번째 줄에 전장의 크기 N, 현재 레벨 K가 주어진다.

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

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

(2 ≤ N ≤ 20, 2 ≤ K ≤ 9)

출력

---

적의 위치 y, x 를 출력한다.

입력의 예 1

5 2
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

출력의 예 1

1 2

입력의 예 2

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

출력의 예 2

4 4

 

풀이

 - 전장속으로 - C에서 풀어서 만들었던

level_list : 레벨 적혀있는 리스트, visite_list :  방문 가능성 리스트, distance_list : 거리 적혀있는 리스트를 이용해서

 - find_min_distande 함수 생성

 - x좌표가 위쪽, y좌표가 왼쪽에 있는 최소값 갱신하면서 최소값 좌표 찾기

from collections import deque

#level_list : 레벨 적혀있는 리스트
#visite_list :  방문 가능성 리스트
#distance_list : 거리 적혀있는 리스트
def put_result(row, attacker_level, level_list, visite_list, distance_list, attacker_x, attacker_y) :
  result_list = [[0] * row for _ in range(row)]
  
  for x in range(row) :
    for y in range(row) :
      if level_list[x][y] != 0 and visite_list[x][y] is True :                #visite_list로 갈수 있는 곳(True) 체크
        if level_list[x][y] == attacker_level :     #레벨이 같은 경우 "."
          result_list[x][y] = "."                   
        if level_list[x][y] < attacker_level :      #작은 경우 거리 출력
          result_list[x][y] = distance_list[x][y]   
      if visite_list[x][y] is False :               #visite_list로 갈수 없는 곳(False) 체크
        if level_list[x][y] > attacker_level :
          result_list[x][y] = "X"                   #갈수 없는 곳중 레벨보다 큰 경우 "X" 
        if level_list[x][y] < attacker_level :
          result_list[x][y] = "-1"

  result_list[attacker_x][attacker_y] = "*"         #공격자 좌표는 *
  
  return result_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_x+1, min_y+1

#공격수 좌표를 시작점으로 갈수있는 곳, 갈수 없는 곳 체크
#공격수 좌표를 시작점으로 거리 구하기
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] = abs(attacker_x - next_x) + abs(attacker_y - next_y)    #틀림 단순 공격자에서 해당 좌표까지 거리
            distance_list[next_x][next_y] = distance_list[now_idx[0]][now_idx[1]] + 1               #공격자가 못가는 경우를 피해서 가는 최단 거리
  
  return find_min_distance(row, attacker_level, level_list, visite_list, distance_list)
  
if __name__ == "__main__":
  row, attacker_level = map(int, input().split())                    #n*n 행렬 너비, 레벨 입력
  data = []
  level_data = []
  result_data = []
  attacker_x = -1                       #공격수 x좌표, y좌표 초기 값은 -1
  attacker_y = -1
  
  for x in range(row) :                 #맵 데이터 입력 받아서 맵 생성
    data = list(map(int, input().split()))
    level_data.append(data)
    
    for y in range(len(data)) :         #입력 받으면서 공격수 9 찾기
      if data[y] == 9 :
        attacker_x = x
        attacker_y = y
  
  min_x, min_y = do_BFS(row, attacker_level, level_data, attacker_x, attacker_y)
  print(min_x, min_y)