-
17086. [Python]아기 상어2Python_알고리즘/Silver II 2023. 9. 26. 01:13
1. 문제
https://www.acmicpc.net/problem/17086
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 512MB
- 브루트포스
- BFS(너비 우선 탐색)
3. 파이썬 코드
from collections import deque # 방향 배열 direction = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] def BFS(start): global max_value # 덱생성 q = deque([start]) while q: check = q.popleft() # 방향배열 순회 for k in range(8): ny = check[0] + direction[k][0] nx = check[1] + direction[k][1] # 범위내 존재할 경우 if ( 0 <= ny < N ) and ( 0 <= nx < M ): # matrix 값이 0인 경우 if matrix[ny][nx] == 0: # 이전값 +1 로 구현 matrix[ny][nx] = matrix[check[0]][check[1]] + 1 # q에 값 추가 q.append((ny,nx)) # matrix 값이 아닌 경우 else: # matrix에 저장된 값이랑 이전값 +1 한 값을 비교하여 작은 경우 if matrix[ny][nx] > matrix[check[0]][check[1]] + 1: # q에 추가 및 값 갱신 q.append((ny,nx)) matrix[ny][nx] = matrix[check[0]][check[1]] + 1 N, M = map(int,input().split()) matrix = [ list(map(int,input().split())) for _ in range(N) ] one_pos = [] # 1인 지점 찾는 반복문 for i in range(N): for j in range(M): if matrix[i][j] == 1: one_pos.append((i,j)) # 최고 값 갱신 변수 max_value = 0 # one_pos 에서 1인 지점 값 뽑아내며 반복 for l in one_pos: BFS(l) # matrix[i][j] 값이 max_value 보다 크면 값 갱신 for i in range(N): for j in range(M): if matrix[i][j] > max_value: max_value = matrix[i][j] print(max_value-1)
4. 문제를 풀고난 후 생각
- 아기 상어의 위치를 찾은 후 아기 상어의 위치를 기준으로 BFS를 적용시킨다.
- 제일 처음 아기 상어의 위치에서 모든 거리를 다 계산해준 후 이후 아기 상어의 좌표에서 이미 값이 있는 곳과 기준이 되는 곳에서 +1 해나간 값들을 비교해가며 작은 값들을 2차원 배열에 갱신해주며 나아간다.
- 이렇게 상어의 좌표에서 모든 BFS 탐색을 진행한 후 matrix 를 순회하며 제일 작은 값을 찾아서 초기 위치 -1 을 해서 답을 출력해주면 원하는 답이 출력된다.
5. 문제를 푸는데 도움이 되는 지식
- BFS
- 방향배열
'Python_알고리즘 > Silver II' 카테고리의 다른 글
1138. [Python]한 줄로 서기 (1) 2023.12.05 15663. [Python]N과 M(9) (1) 2023.10.03 18870. [Python]좌표 압축 (0) 2023.09.04 2644. [Python]촌수계산 (0) 2023.09.04 5002. [Python]도어맨 (1) 2023.08.27