[백준][BFS] 16236. 아기상어

16236. 아기상어

16236번: 아기 상어

 

다른 사람 풀이 (python)

• 📍bfs 함수를 메인의 for문 안에서 반복적으로 호출하는 경우
  • 바뀐 map을 새로 전달해줘야하는지, 원본 map을 줘야하는지 주의!!!
  • 매번 새로 초기화해줘야하는 변수나 배열 뭔지 확인할 것! 
    • -> 여기서는 fish, visited 매번 초기화
• visited로 거리계산하는 경우 -1로 초기화해서 방문하지 않은 곳은 0이 아닌 -1로 해야 0부터 거리계산하기 편하다
• ⚠️Error 찾느라 오래걸린 부분:
  • 작거나같은 경우 지나갈수 있음
  • 하지만, 작은 경우에만 먹을 수 있음
    • fish저장하는 범위를 1<=map[nx][ny]<=size 라고 범위 잘못지정해서 에러
• lambda식 이용하여 정렬

• 받아온 결과물이 비어있는지 확인! 이런 부분이 생각하기 어려울수있음!
• if len(result)==0: # 비어있으면
          print(time)
          break

import sys
input=sys.stdin.readline

from collections import deque

n=int(input())
size=2 # 상어의 처음 크기
map=[list(map(int,input().split())) for _ in range(n)]
queue=deque()

dx=[-1,1,0,0]
dy=[0,0,-1,1]

shark_x, shark_y=0,0

for i in range(n):
    for j in range(n):
        if map[i][j]==9:
            shark_x=i
            shark_y=j
            map[i][j]=0
          

#변경된 map을 전해줘야함
def bfs(map,r,c,size): #현재위치에서 먹으러갈 수 있는 물고기 중 가장 가까운 위치 반환
  ####중요: fish랑 visited를 bfs내에서 초기화해줘야한다###
  #-> 새로온 위치에서 갈수있는 fish는 매번 달라지기때문에
    fish=[]
    #0부터 거리계산에 쓰기위해서 방문하지 않은 곳은 -1로 초기화
    visited=[[-1 for _ in range(n)] for _ in range(n)]
  
    queue.append((r,c))
    visited[r][c]=0 #방문확인을 위해 처음에 1로 설정 -> 이후 계산시 -1 빼줘야함
    
    while queue:
        x,y=queue.popleft()
       
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
        
            if 0<=nx<n and 0<=ny<n:
                if visited[nx][ny]==-1 and map[nx][ny]<=size: #자기보다 작거나같은 물고기인경우 지나갈수있음
                    visited[nx][ny]=visited[x][y]+1
                    queue.append((nx,ny))
                  
                    if 1<=map[nx][ny]<size: #자기보다 작은 물고기만 먹을수 있음
                        fish.append((visited[nx][ny], nx,ny))

    
    return sorted(fish,key= lambda x: (x[0],x[1],x[2])) 
  

cnt=0
time=0
while True:
    #거리가 가까운 fish부터 방문
    result= bfs(map,shark_x, shark_y,size) #while문 돌면서 변경되는 map을 다시 전달해줘야함
    
    
    if len(result)==0: # 비어있으면
        print(time)
        break
  
    fdist, fx, fy =result.pop(0)
    map[fx][fy]= 0 #물고기 먹음
    time+=fdist #물고기 먹으러간 거리(시간)더해주기
    
    cnt+=1
    if cnt==size:
        size+=1
        cnt=0
  
    shark_x, shark_y=fx,fy

 

• 위 코드 파라미터 수정
• 메인에서 정의해놓은 map, size 변경되어도 파라미터에 새로 넣지 않아도됨
  • 파라미터에서 map,size 지워도 정답

import sys
input=sys.stdin.readline

from collections import deque

n=int(input())
size=2 # 상어의 처음 크기
map=[list(map(int,input().split())) for _ in range(n)]
queue=deque()

dx=[-1,1,0,0]
dy=[0,0,-1,1]

shark_x, shark_y=0,0

for i in range(n):
    for j in range(n):
        if map[i][j]==9:
            shark_x=i
            shark_y=j
            map[i][j]=0
          

#변경된 map을 전해줘야함
def bfs(r,c): #현재위치에서 먹으러갈 수 있는 물고기 중 가장 가까운 위치 반환
  ####중요: fish랑 visited를 bfs내에서 초기화해줘야한다###
  #-> 새로온 위치에서 갈수있는 fish는 매번 달라지기때문에
    fish=[]
    #0부터 거리계산에 쓰기위해서 방문하지 않은 곳은 -1로 초기화
    visited=[[-1 for _ in range(n)] for _ in range(n)]
  
    queue.append((r,c))
    visited[r][c]=0 #방문확인을 위해 처음에 1로 설정 -> 이후 계산시 -1 빼줘야함
    
    while queue:
        x,y=queue.popleft()
       
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
        
            if 0<=nx<n and 0<=ny<n:
                if visited[nx][ny]==-1 and map[nx][ny]<=size: #자기보다 작거나같은 물고기인경우 지나갈수있음
                    visited[nx][ny]=visited[x][y]+1
                    queue.append((nx,ny))
                  
                    if 1<=map[nx][ny]<size: #자기보다 작은 물고기만 먹을수 있음
                        fish.append((visited[nx][ny], nx,ny))

    
    return sorted(fish,key= lambda x: (x[0],x[1],x[2])) 
  

cnt=0
time=0
while True:
    #거리가 가까운 fish부터 방문
    result= bfs(shark_x, shark_y) #while문 돌면서 변경되는 map을 다시 전달해줘야함
    
    
    if len(result)==0: # 비어있으면
        print(time)
        break
  
    fdist, fx, fy =result.pop(0)
    map[fx][fy]= 0 #물고기 먹음
    time+=fdist #물고기 먹으러간 거리(시간)더해주기
    
    cnt+=1
    if cnt==size:
        size+=1
        cnt=0
  
    shark_x, shark_y=fx,fy

 

---

자바 코드: https://yygs321.tistory.com/319