전장속으로 - A

문제

N x N 행렬에 0 이상의 정수가 주어질 때, 0 이 아닌 숫자 중 최솟값을 찾아 해당 좌표를 출력해보자. 만약 최솟값이 2개 이상일 경우 가장 위쪽에 존재하는 숫자를 출력하고, 가장 위쪽에 존재하는 숫자가 여러 개일 경우 그 중에서도 가장 왼쪽에 존재하는 숫자를 출력한다.

위와 같이 숫자가 주어졌다고 하자. 최솟값은 색칠이 되어있는 칸인 (1, 2), (1, 4), (5, 1) 이다. 이 중에서 가장 위쪽이면서 왼쪽 위치는 (1, 2) 이다.

입력

---

첫 번째 줄에 행렬의 크기 N이 주어진다. 두 번째 줄부터 N 개의 줄에 걸쳐 숫자가 주어진다. 각 줄은 N개의 숫자로 이루어져 있다. 각 숫자는 0 이상 10,000 이하의 정수이다. 왼쪽 최상단의 좌표는 (1, 1)이다.

(2 ≤ N ≤ 20)

출력

---

0이 아닌 숫자 중 가장 작은 값의 y 좌표, x 좌표 순서대로 공백을 통해 구분하여 출력한다.

입력의 예 1

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

출력의 예 1

1 2

입력의 예 2

9
3 23 85 34 17 74 25 52 65
10 7 39 42 88 52 14 72 63
87 42 18 78 53 45 18 84 53
34 28 64 85 12 16 75 36 55
21 77 45 35 28 75 90 76 1
25 87 65 15 28 11 37 28 74
65 27 75 41 7 89 78 64 39
47 47 1 45 23 65 3 41 44
87 13 82 38 31 12 29 29 80

출력의 예 2

5 9

 

풀이 1

 - BFS로 풀라고 해서 BFS로 풀었는데 너무 복잡하게 풀었다

 - 0,0부터 시작해서 BFS 돌면서 최소값 찾고 찾을때 마다 최소값 : x좌표, y좌표를 딕셔너리에 저장

 - 딕셔너리 저장 후 data_list.sort(key=lambda x: (x[0], x[1]))이용해서 키 정렬(x좌표는 내림차순, x가 같으면 y좌표는 오름차순)

 - 여기에서 BFS를 활용하라는게 아니였나보다.....

 - 다시 풀자

from collections import deque
  
#BFS 현재 좌표는 pop, 다음으로 갈 인접 좌표 큐에 push
def BFS(start_x, start_y) :
  dx = [-1, 0, 1, 0]                    #위 0, 오른 1, 아래쪽 2, 왼쪽 3
  dy = [0, 1, 0, -1]
  
  dq = deque()                          #BFS를 위한 큐 생성
  
  min_value = 10001                   #최소값 시작
  min_index = [-1, -1]                #최소값 시작 좌표 -1, -1
  min_dic = {}

  #첫번째 입력값 최소값 비교 및 딕셔너리로 저장 [최소값 : [x좌표, y좌표]
  if map_data[start_x][start_y] != 0 and map_data[start_x][start_y] <= min_value  :    #시작 값이 0이 아니고, 제일 작은 값인경우 min 데이터 갱신
    min_value = map_data[start_x][start_y]
    min_index[0] = start_x
    min_index[1] = start_y
    if min_value not in min_dic.keys() :
      min_dic[min_value] = [[min_index[0], min_index[1]]]
    else :
      min_dic[min_value].append([min_index[0], min_index[1]])
      
  dq.append((start_x, start_y))         #1. 큐에 시작점 추가
  map_data[start_x][start_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) and map_data[next_x][next_y] is not True:    #테두리 이상 벗어나지 않는 조건, 이미 방문한 곳은 재방문 하지않음
        #최소값 찾기 : min_value보다 작은 값 갱신, x좌표 y좌표 갱신
        if map_data[next_x][next_y] != 0 and map_data[next_x][next_y] <= min_value :
          min_value = map_data[next_x][next_y]    #최소 값
          min_index[0] = next_x                   #최소 값 x좌표
          min_index[1] = next_y                   #최소 값 y좌표
          
          #최소값 찾은 후 딕셔너리로 찾은 최소값 목록 저장 "최소값 : [x좌표, y좌표]"
          if min_value not in min_dic.keys() :
            min_dic[min_value] = [[min_index[0], min_index[1]]]
          else :
            min_dic[min_value].append([min_index[0], min_index[1]])
          
        map_data[next_x][next_y] = True           #방문한 곳은 재방문 방지를 위해 True 처리
        dq.append((next_x, next_y))
  return min_dic

#x값은 작게, y값은 크게
def compare_min_position(data_list) :
  data_list.sort(key=lambda x: (x[0], x[1]))      #0번째걸로 먼저 정렬, 같은 값이 나온 경우 내림 차순 정렬
  return data_list[0]

if __name__ == "__main__":

  row = int(input())                    #n*n 행렬 너비 입력
  map_data = []
  min_find_dic = {}
  
  for i in range(row) :                 #맵 데이터 입력 받아서 맵 생성
    map_data.append(list(map(int, input().split())))
  
  min_find_dic = BFS(0, 0)
  result = compare_min_position(min_find_dic[min(min_find_dic.keys())])
  print(result[0]+1, result[1]+1)

 

풀이2

 - 입력 받으면서 "윗줄에 있을수록, 왼쪽에 있을수록"이 조건에서 말하는 최소값이다라는 판단

if __name__ == "__main__":

  row = int(input())                    #n*n 행렬 너비 입력
  map_data = []                         #맵 전체 정보 저장
  data = []
  min_value = 10001
  min_x = -1
  min_y = -1
  
  for i in range(row) :                             #맵 데이터 입력 받아서 맵 생성
    data = list(map(int, input().split()))
    map_data.append(data)                           #이차원 리스트로 map_data 생성
    
    #최소값 찾기(동일한 최소값인 경우 가장 위쪽에 존재, 가장 왼쪽에 존재)
    for j in range(len(data)) :
      if data[j] != 0 and data[j] < min_value :     #0이 아니고, 찾았던 최소값보다 작은 경우
        min_value = data[j]                         #최소값 갱신
        min_x = i                                   #최소값 x좌표 갱신
        min_y = j                                   #최소값 y좌표 갱신
    
  print(min_x+1, min_y+1)                           #결과 값
  #print(map_data)