[Python] 16236번 아기 상어

https://www.acmicpc.net/problem/16236

 

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

def move(y,x):
    fishlist[y][x]=0 # <-첫시작 부분

    #먹을 수 있는 물고기 위치 담기
    fishs=[]
    for i in range(N):
        for j in range(N):
            if 0<fishlist[i][j]<shark_size:
                fishs.append([i,j])
    
    #물고기별 거리,위치 구하기
    res=[] #물고기별 거리,위치 담을 리스트
    for fish in fishs:
        queue=[[y,x,0]]
        visited=[[False for _ in range(N)] for _ in range(N)]
        visited[y][x]=True

        find_fish=False
        while queue:
            if find_fish:
                break

            qy,qx,qd=queue.pop(0)
            for d in range(4):
                ny=qy+dy[d]
                nx=qx+dx[d]
                nd=qd+1

                if 0<=ny<N and 0<=nx<N:
                    #먹을려는 물고기에 도달하면 stop
                    if ny==fish[0] and nx==fish[1]:
                        res.append([nd,ny,nx])
                        find_fish=True
                        break

                    if fishlist[ny][nx]<=shark_size: #지나갈 수 있는 물고기인지
                        if not visited[ny][nx]:
                            visited[ny][nx]=True
                            queue.append([ny,nx,nd])
    
    return res

#1.입력
N=int(input())
fishlist=[list(map(int,input().split())) for _ in range(N)]
#2.자료형 정의

#3.동작함수
# 아기상어 위치 찾기 -> 9인 곳 찾기
for y in range(N):
    for x in range(N):
        if fishlist[y][x]==9:
            sy,sx=y,x #상어가 있는 곳

shark_size=2
shark_cnt=0
distance=0
while True:
    ans=move(sy,sx)
    if ans: #물고기를 먹었다면
        ans=sorted(ans,key=lambda x:(x[0],x[1],x[2]))
        distance+=ans[0][0]
        sy,sx=ans[0][1],ans[0][2]

        shark_cnt+=1
        if shark_cnt==shark_size:
            shark_size+=1
            shark_cnt=0

    else: #물고기를 먹지 못했다면
        break     

#4.출력
print(distance)

 

 

---

처음 틀렸던 코드....

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

def move(iy,ix):
    queue=[[iy,ix,0]]
    visited=[[False for _ in range(N)] for _ in range(N)]
    visited[iy][ix]=True #<-현재 상어가 있는 곳 방문처리

    #가장 가까운 물고기 찾기
    while queue:
        y,x,dist=queue.pop(0)
        for d in range(4):
            ny=y+dy[d]
            nx=x+dx[d]
            if 0<=ny<N and 0<=nx<N: #범위를 넘지 않고
                if not visited[ny][nx]: #방문하지 않았다면
                    if matrix[ny][nx]<=shark: #상어 크기보다 작다면
                        if matrix[ny][nx]!=0 and matrix[ny][nx]<shark: #먹을 수 있다면
                            matrix[ny][nx]=0 #물고기 먹기
                            #print("can eat!!",ny,nx,"shark=",shark)
                            print("shark",shark)
                            for mit in matrix:
                                print(mit)
                            print()
                            return [dist+1,ny,nx]
                        else: #움직을 수만 있다면
                            visited[ny][nx]=True
                            queue.append([ny,nx,dist+1])                   
    return [0]

#1.입력
N=int(input())
matrix=[list(map(int,input().split())) for _ in range(N)]
#2.자료형 정의

#3.동작함수
# 아기상어 위치 찾기 -> 9인 곳 찾기
for y in range(N):
    for x in range(N):
        if matrix[y][x]==9:
            sy,sx=y,x #상어가 있는 곳

matrix[sy][sx]=0 #<-첫시작 부분
shark=2
shark_cnt=0
distance=0
while True:
    m=move(sy,sx)
    #print(m)

    if m[0]==0: #만약 더 이상 움직일 수 없다면
        break
    else:
        shark_cnt+=1 #현재 물고기 먹은 횟수
        if shark_cnt==shark: #아기 상어가 자신의 크기와 같은 수의 물고기 먹으면 크기 1 증가
            shark+=1
            shark_cnt=0

        distance+=m[0]
        sy,sx=m[1],m[2]

#4.출력
print(distance)

이건 처음 잘못 풀었던 코드인데

여기서 출력을 해보면

....

shark 4
[5, 4, 0, 0, 3, 4]
[4, 3, 0, 3, 4, 5]
[3, 2, 0, 5, 6, 6]
[2, 0, 0, 3, 4, 5]
[3, 2, 0, 6, 5, 4]
[6, 6, 6, 6, 6, 6]

shark 4
[5, 4, 0, 0, 3, 4]
[4, 0, 0, 3, 4, 5]
[3, 2, 0, 5, 6, 6]
[2, 0, 0, 3, 4, 5]
[3, 2, 0, 6, 5, 4]
[6, 6, 6, 6, 6, 6]

....

다음과 같이 동작하는데

파란색으로 이동해야 할 것이 빨간색으로 이동하여 물고기를 먹고 0으로 된 것을 볼 수 있다.