[ BOJ / Python ] 16236번 아기 상어
이번 문제는 BFS를 이용하여 갈 수 있는 공간 중 조건에 부합하는 위치로 이동하는 과정을 더이상 움직일 수 없을 때까지 반복하는 방식으로 접근하였다. 답을 찾아보지 않고 풀이하여 시간이 오래 걸렸지만 그만큼 얻은게 많은 문제이다.
- n을 입력받는다.
- 공간을 grid에 입력받는다.
- 상어의 위치를 나타내는 변수 cur_y, cur_x를 0으로 선언한다.
- n번 반복하는 i에 대한 for문을 돌린다.
-> n번 반복하는 j에 대한 for문을 돌린다.
--> 만약 grid[i][j]가 9일 경우,
---> cur_y, cur_x를 i, j로 갱신한다.
---> grid[i][j]를 0으로 갱신한다.
---> 반복문을 종료한다. - 아기 상어의 크기에 해당하는 변수 baby를 2로 선언한다.
- 방향에 해당하는 리스트 dy, dx를 상, 좌, 우, 하 순서로 저장한다.
- bfs함수를 cur_y, cur_x를 인자로 갖도록 선언한다.
-> q를 deque로 선언한다.
-> q에 (0, cur_y, cur_x, 0)을 넣는다.
-> 방문 처리 리스트 visited를 n*n의 크기로 선언하고, False를 채운다.
-> visited[cur_y][cur_x]를 True로 갱신한다.
-> 잡아 먹을 수 있는 물고기의 위치를 저장할 리스트 results를 선언한다.
-> q가 존재하는 동안 반복하는 while문을 돌린다.
--> d, y, x, flg를 q에서 추출한다.
--> 최소 거리를 저장할 변수 md를 sys.maxsize로 선언한다.
--> 만약 flg가 1이고, d가 md보다 작거나 같을 경우,
---> md를 d로 갱신한다.
---> results에 (d, y, x)를 넣는다.
--> 4번 반복하는 i에 대한 for문을 돌린다.
---> ny, nx를 y+dy[i], x+dx[i]로 갱신한다.
---> 만약 ny가 0 이상, n 미만이고, nx가 0 이상, n 미만이고, visited[ny][nx]가 False일 경우,
----> 만약 grid[ny][nx]가 0보다 크고, baby보다 작을 경우,
-----> visited[ny][nx]를 True로 갱신한다.
-----> q에 (d+1, ny, nx, 1)을 넣는다.
----> 만약 grid[ny][nx]가 baby와 같거나 grid[ny][nx]가 0일 경우,
-----> visited[ny][nx]를 True로 갱신한다.
-----> q에 (d+1, ny, nx, 0)을 넣는다.
-> 만약 results가 비어있을 경우,
--> [-1, -1, -1]을 출력한다.
-> results를 오름차순 정렬한다.
-> results[0]을 반환한다. - 결과를 저장할 변수 answer를 0으로 선언한다.
- 카운팅 변수 cnt를 0으로 선언한다.
- while문을 돌린다.
-> time, cur_y, cur_x를 bfs(cur_y, cur_x)로 저장한다.
-> 만약 [time, cur_y, cur_x]가 [-1, -1, -1]과 같을 경우,
--> answer를 출력한다.
--> while문을 종료한다.
-> answer에 time을 더한다.
-> grid[cur_y][cur_x]를 0으로 선언한다.
-> cnt를 1 증가시킨다.
-> 만약 cnt가 baby와 같을 경우,
--> baby를 1 증가시킨다.
--> cnt를 0으로 갱신한다.
Code
import sys
from collections import deque
n=int(input())
grid=[list(map(int, input().split())) for _ in range(n)]
cur_y, cur_x=0, 0
for i in range(n):
for j in range(n):
if grid[i][j]==9:
cur_y, cur_x=i, j
grid[i][j]=0
break
baby=2
dy, dx=[-1, 0, 0, 1], [0, -1, 1, 0]
def bfs(cur_y, cur_x):
q=deque()
q.append((0, cur_y, cur_x, 0))
visited=[[False]*n for _ in range(n)]
visited[cur_y][cur_x]=True
results=[]
while q:
d, y, x, flg=q.popleft()
md=sys.maxsize
if flg==1 and md>=d:
md=d
results.append((d, y, x))
for i in range(4):
ny, nx=y+dy[i], x+dx[i]
if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
if 0<grid[ny][nx]<baby:
visited[ny][nx]=True
q.append((d+1, ny, nx, 1))
elif grid[ny][nx]==baby or grid[ny][nx]==0:
visited[ny][nx]=True
q.append((d+1, ny, nx, 0))
if not results:
return [-1, -1, -1]
results.sort(key=lambda x: (x[0], x[1], x[2]))
return results[0]
answer=0
cnt=0
while True:
time, cur_y, cur_x=bfs(cur_y, cur_x)
if [time, cur_y, cur_x]==[-1, -1, -1]:
print(answer)
break
answer+=time
grid[cur_y][cur_x]=0
cnt+=1
if cnt==baby:
baby+=1
cnt=0
import sys
from collections import deque
n=int(input())
grid=[list(map(int, input().split())) for _ in range(n)]
cur_y, cur_x=0, 0
for i in range(n):
for j in range(n):
if grid[i][j]==9:
cur_y, cur_x=i, j
grid[i][j]=0
break
baby=2
dy, dx=[-1, 0, 0, 1], [0, -1, 1, 0]
def bfs(cur_y, cur_x):
q=deque()
q.append((0, cur_y, cur_x, 0))
visited=[[False]*n for _ in range(n)]
visited[cur_y][cur_x]=True
results=[]
while q:
d, y, x, flg=q.popleft()
md=sys.maxsize
if flg==1 and md>=d:
md=d
results.append((d, y, x))
for i in range(4):
ny, nx=y+dy[i], x+dx[i]
if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
if 0<grid[ny][nx]<baby:
visited[ny][nx]=True
q.append((d+1, ny, nx, 1))
elif grid[ny][nx]==baby or grid[ny][nx]==0:
visited[ny][nx]=True
q.append((d+1, ny, nx, 0))
if not results:
return [-1, -1, -1]
results.sort(key=lambda x: (x[0], x[1], x[2]))
return results[0]
answer=0
cnt=0
while True:
time, cur_y, cur_x=bfs(cur_y, cur_x)
if [time, cur_y, cur_x]==[-1, -1, -1]:
print(answer)
break
answer+=time
grid[cur_y][cur_x]=0
cnt+=1
if cnt==baby:
baby+=1
cnt=0
Author And Source
이 문제에 관하여([ BOJ / Python ] 16236번 아기 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-16236번-아기-상어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)