08/28 아기상어 BOJ 16236 파이썬

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

16236번: 아기 상어

전형적인 삼성 DFS/BFS + 구현 문제 였다.

규칙이 복잡하게 구성되어 있기 때문에 구조를 먼저 짠 후에 코드를 작성하도록 하자

 

1. 초기 상어의 위치를 알아내고 상어위치에 있는 값을 0으로 바꾸어준다.

반복문

1.  상어의 위치 주변에 먹을 수 있는 물고기가 있는지 확인한다.

2. 있으면 먹은 후 시간, 먹은 횟수, 사이즈, 상어의 위치를 업데이트 한 후 continue를 통해 1과정을 반복한다.

3. 만약 인접한 위치에 먹을 수 있는 물고기가 없다면 상어의 위치에서 BFS를 수행하면서 먹을 수 있는 물고기의 (거리, row, col)을 리스트에 추가해주고 거리, row, col를 오름 차순으로 정렬해준다.

4. 가장 가까운 물고기에 대해 거리를 이동하고 시간, 먹은 횟수, 사이즈, 상어의 위치를 업데이트 한다.

5. 만약 먹을 수 있는 물고기가 없으면 종료한다.

 

N=int(input())

sea = [list(map(int, input().split())) for i in range(N)]
feed_count =0
size  =2
for i in range(N):
    for j in range(N):
        if sea[i][j] == 9:
           loc_shark = (i, j)
           sea[i][j]=0

moves = [(-1,0), (0,-1), (0,1), (1,0)]

def distance(loc_shark): #sea 전체를 스캔하면서 먹이의 위치를 찾는 함수
    q =[loc_shark]
    visited=[[0 for i in range(N)] for i in range(N)]
    while q:
        r, c =q.pop(0)
        for dr, dc in moves:
            nr = r + dr
            nc = c + dc
            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0 and 0<= sea[nr][nc] <= size:
                visited[nr][nc] = visited[r][c] +1
                q.append((nr, nc))
    return visited

def findfeed(loc_shark,feed_count): #먹이 위치와 거리 값 반환
    temp =[]
    disMat =distance(loc_shark)
    for i in range(N):
        for j in range(N):
            if disMat[i][j] !=0 and 0< sea[i][j] <size:
                temp.append((disMat[i][j], i, j))
    #거리/행/열 순으로 오름 차순 정렬
    temp =sorted(temp, key = lambda x :x[2])
    temp = sorted(temp, key=lambda x: x[1])
    temp = sorted(temp, key=lambda x: x[0])

    if not temp:
        return False ,None
    return True, temp[0]



'''
가장 가까운 물고기를 갖고 있어야된다.
만약에 먹이가 인접해 있으면 가서 먹으면 됨
주변에 모두 바다 밖에 없으면 거리를 계산해서 
크기가 큰 물고기가 있는 지점에 대해서는 거리를 알지 못하기 때문에 BFS로 알아야한다.
'''


def adjfeedFinder(loc_shark, feed_count,size):
    for dr, dc in moves:
        nr = loc_shark[0] + dr
        nc = loc_shark[1] + dc
        if 0<= nr <N and 0 <= nc <N and 0 < sea[nr][nc] <size:
            if sea[nr][nc] < size:
                feed_count += 1
                sea[nr][nc] = 0
                return True, [size, feed_count, (nr, nc)]

        return False, None

time =0
while True:
    IsFeedAdj, Value = adjfeedFinder(loc_shark, feed_count, size)
    if IsFeedAdj:
        size, feed_count, loc_shark = Value
        time += 1
        if feed_count == size:
            size +=1
            feed_count =0
        continue

    IsFeed, Value = findfeed(loc_shark, feed_count)
    if Value== None:

        break
    else:

        dis, *loc_shark=Value
        time += dis
        sea[loc_shark[0]][loc_shark[1]] = 0
        feed_count += 1
        if feed_count == size:
            size +=1
            feed_count =0


print(time)

 

다른 사람 풀이

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

def bfs():
    global shark_eat, fish_count, shark_size 
    start = [(shark_x, shark_y)] #상어 위치와 먹이를 담을 리스트
    queue =[] #이동을 담을 리스트
    times = 0

    while start:
        p = start.pop()
        visitied = [[0]*N for _ in range(N)]
        visitied[p[0]][p[1]] = 1 #상어 위치 방문 표기
        size = 1 
        queue.append(p) #처음 상어위치로부터 출발하므로 이동을 담는 리스트 queue에 넣어준다.
        if fish_count == 0: #먹을 수 없는 물고기가 없다면 종료
            break
            
        while queue:  #이동을 더 이상할 수 없을 때까지
            for _ in range(size):
                q = queue.pop(0)
                for i in range(4): #인접한 위치에 대해서
                    nx = q[0] + dx[i]
                    ny = q[1] + dy[i]
                    if 0 <= nx < N and 0 <= ny < N and visitied[nx][ny] == 0 and (sea[nx][ny] == shark_size or sea[nx][ny] == 0):
                        #바다(0)이거나 동일한 크기의 물고기면 이동만 가능하므로
                        queue.append((nx, ny)) 
                        visitied[nx][ny] = visitied[q[0]][q[1]]+1
                        
                    elif 0 <=nx < N and 0 <= ny < N and sea[nx][ny] != 0 and shark_size > sea[nx][ny] and visitied[nx][ny] == 0:
                        #먹을 수 있는 먹이는 start에 담아 준다
                        start.append((nx, ny))
                        visitied[nx][ny] = visitied[q[0]][q[1]] + 1
                        
            if len(start): 
            #만약 start값이 있으면 먹을 수 있는 먹이중 가장 가까운 값을 찾는다.
                sx, sy = start[0][0], start[0][1] 
              
               
                for x, y in start: #for 문을 돌면서 가장 가까운 거리에 있는 값을 찾는다.
                    if x < sx:
                        sx = x
                        sy = y
                    elif x == sx and y < sy:
                        sx = x
                        sy = y
                        
                shark_eat += 1
                if shark_eat == shark_size: #사이즈 업데이트
                    shark_size += 1
                    shark_eat = 0
                sea[p[0]][p[1]] = 0 #처음 상어의 치는 초기화
                sea[sx][sy] = 9 #상어 위치 옮기기
                
                queue = []
                fish_count -= 1 
                times += visitied[sx][sy]-1 #거리가 저장되어 있음
                start = [(sx,sy)]
                break #먹이를 하나 먹었으면 바로 위치가 업데이트 되었으므로 바로 빠져나온다.
            size = len(queue)

    return times


N = int(input())

sea = [list(map(int, input().split())) for _ in range(N)]
shark_x = shark_y = 0
fish_count = 0
fish_cnt =[]
for i in range(N):
    for j in range(N):
        if sea[i][j] == 9:
            shark_x, shark_y = i, j
        elif sea[i][j] != 0:
            fish_count += 1

shark_size = 2
shark_eat = 0

result = bfs()
print(result)