본문 바로가기
Algorithm

[탐색/BFS] 백준 16236 아기 상어 - 파이썬(Python)

by jangThang 2022. 3. 24.
반응형

백준 온라인 저지

 

[ Contents ]

     

     

    1. 문제 (링크 참조)

     

    16236번: 아기 상어

    N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

    www.acmicpc.net

     

     

    2. 문제 풀이

     아기 상어가 먹을 수 있는 먹잇감을 모두 먹는 데에 걸리는 시간을 구하는 문제입니다. 자신보다 작은 물고기만 먹을 수 있고, 크기 2부터 시작합니다. 자신보다 큰 물고기는 통과할 수 없으며, 자신과 동일한 크기면 통과할 수 있습니다.

     

    2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

     

    [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

     BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath First Search) 너비 우선 탐색(BFS): 가까운 주변 노드부터 탐색하며 점점.

    star7sss.tistory.com

     BFS탐색을 이용해서 '현재 위치'에서 자신이 먹을 수 있는 물고기를 탐색합니다. 동일한 거리에 있을 경우에는 '위', '왼쪽'에 있는 물고기를 먼저 먹습니다.

     

     

     

    3. 코드

    from collections import deque
    import sys
    input = sys.stdin.readline
    
    #입력
    N = int(input())
    sea = []  # 그래프
    startX, startY = 0, 0 # 아기상어 위치
    for i in range(N):
        lst = list(map(int, input().split()))
        for j in range(N):
            if lst[j] == 9:
                lst[j] = 0  # 크기가 9인 물고기로 오인하지 않도록
                startX, startY = i, j  # 아기상어 위치
        sea.append(lst)

     물고기 위치를 입력받고, 아기 상어의 위치를 저장합니다. 아기 상어의 위치는 9로 입력되며, 크기가 9인 물고기로 오인하지 않도록 0으로 바꿔줍니다.

     

     

    # BFS탐색
    direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]  # 상하좌우
    size = 2
    move = 0
    eat = 0
    
    while True:
        visited = [[False] * N for _ in range(N)]  # 방문표시
        queue = deque([(startX, startY, 0)])  # 시작 위치
        visited[startX][startY] = True
        flag = 9999 # 먹을 수 있는 물고기 탐색여부
        fish = []  # 물고기 위치
        while queue:
            x, y, cnt = queue.popleft()
            if cnt > flag:
                break
    
            #상하좌우 탐색
            for dx, dy in direction:
                nx, ny = x+dx, y+dy
                # 범위를 벗어나지 않고, 자신이 지나갈 수 있는 미방문인 곳을 탐색
                if 0 <= nx < N and 0 <= ny < N and sea[nx][ny] <= size and not visited[nx][ny]:
                    visited[nx][ny] = True  # 방문
                    queue.append((nx, ny, cnt+1))
                    # 자신보다 작은 물고기가 있으면 먹음
                    if 0 < sea[nx][ny] < size:
                        fish.append((nx, ny, cnt+1))
                        flag = cnt  # 탐색완료

     아기 상어 위치에서 가장 가까운 먹잇감 위치를 BFS 탐색합니다. 자신보다 작은 먹잇감을 찾았으면, queue에 넣고 해당 위치에서 다시 BFS 탐색할 준비를 합니다.

     

     

        # 먹을 수 있는 물고기가 있으면 계속 탐색
        if fish:
            fish.sort() #위, 왼쪽 물고기 먼저 먹음
            x, y, dist = fish[0] #먹을 물고기 위치와 필요한 이동거리
            sea[x][y] = 0 #먹고나면 빈 칸
            move += dist
    
            # 먹은 물고기 횟수+1, 사이즈와 동일하다면 사이즈업
            eat += 1
            if eat == size:
                size += 1
                eat = 0
            startX, startY = x, y
    
        # 더이상 먹을 수 있는 물고기 없음
        else:
            break
    print(move)

     print(move)를 제외하곤 while True 반복문 안입니다. BFS탐색에서 찾은 물고기 중 거리가 가장 짧은 물고기를 먹습니다. 거리가 같다면 가장 위, 왼쪽인 물고기를 먼저 먹습니다. (거리, 행, 열 순으로 오름차순 정렬)

     먹고 난 물고기칸은 빈 칸(0)이 되고, 해당 거리만큼 시간을 더해줍니다. (1초에 1칸 이동) 먹은 물고기 횟수를 +1 해주고, 사이즈와 동일해졌다면 사이즈를 올려줍니다. 이후 시작 지점을 먹은 물고기 칸(x, y)으로 갱신하고 BFS 탐색을 진행합니다.

     만약 더 이상 먹을 수 있는 물고기가 없다면 탐색을 종료합니다.

     

     

    cf) Flag 오류

    from collections import deque
    import sys
    input = sys.stdin.readline
    
    #입력
    N = int(input())
    sea = []  # 그래프
    startX, startY = 0, 0 # 아기상어 위치
    for i in range(N):
        lst = list(map(int, input().split()))
        for j in range(N):
            if lst[j] == 9:
                lst[j] = 0  # 크기가 9인 물고기로 오인하지 않도록
                startX, startY = i, j  # 아기상어 위치
        sea.append(lst)
    
    # BFS탐색
    direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]  # 상하좌우
    size = 2
    move = 0
    eat = 0
    
    while True:
        visited = [[False] * N for _ in range(N)]  # 방문표시
        queue = deque([(startX, startY, 0)])  # 시작 위치
        visited[startX][startY] = True
        flag = False # 먹을 수 있는 물고기 탐색여부
        fish = []  # 물고기 위치
        while queue:
            x, y, cnt = queue.popleft()
            if flag:
                break
    
            #상하좌우 탐색
            for dx, dy in direction:
                nx, ny = x+dx, y+dy
                # 범위를 벗어나지 않고, 자신이 지나갈 수 있는 미방문인 곳을 탐색
                if 0 <= nx < N and 0 <= ny < N and sea[nx][ny] <= size and not visited[nx][ny]:
                    visited[nx][ny] = True  # 방문
                    queue.append((nx, ny, cnt+1))
                    # 자신보다 작은 물고기가 있으면 먹음
                    if 0 < sea[nx][ny] < size:
                        fish.append((nx, ny, cnt+1))
                        flag = True  # 탐색완료
    
        # 먹을 수 있는 물고기가 있으면 계속 탐색
        if fish:
            fish.sort() #위, 왼쪽 물고기 먼저 먹음
            x, y, dist = fish[0] #먹을 물고기 위치와 필요한 이동거리
            sea[x][y] = 0 #먹고나면 빈 칸
            move += dist
    
            # 먹은 물고기 횟수+1, 사이즈와 동일하다면 사이즈업
            eat += 1
            if eat == size:
                size += 1
                eat = 0
            startX, startY = x, y
    
        # 더이상 먹을 수 있는 물고기 없음
        else:
            break
    print(move)

     위 정답코드와 달리, flag를 bool 변수로 두었습니다. break 조건을 cnt > flag로 두지 않으면, 거리가 같은 다른 물고기를 탐색하지 못합니다.

     

    5
    3 3 2 4 3
    1 4 5 3 1
    1 4 3 3 2
    4 3 2 3 1
    3 3 1 3 9
    
    정답: 31
    출력: 34

     위 예제를 살펴보면 12초에서 잘못된 선택을 합니다.

     

     본래라면 상단이고 왼쪽인 물고리를 먹어야 합니다. (아기 상어의 위치를 9로 표시)

     

     하지만, 위 코드는 12초에서 오른쪽 상단의 물고기를 먹습니다. (먹은 물고기 자리를 -1로 표시)

     먹잇감만 찾으면, 1~3번의 탐색 뒤에 발견될 동일한 거리의 먹잇감이 무시되기 때문입니다. 따라서 cnt > flag로 동일 거리의 먹잇감 탐색이 이루어지도록 조정하면, 정답 코드가 됩니다.

     

    star가 되고나서 Tistory

    반응형

    댓글