BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이

📚 문제

링크: https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

👨‍💻 접근법

⚙️ 활용 알고리즘: BFS

 

주어진 맵(i.e., 그래프)에서 아기상어와 떨어진 거리(i.e., 안전거리)의 최댓값을 구하는 문제입니다.

처음 생각한 아이디어는 상어가 없는(i.e., 빈칸) 노드에서부터 상어까지의 최소 거리를 구하는 것이었습니다.

하지만 해당 접근법은 연산 비용이 클 거라는 생각이 들었습니다.

이에 연산 비용을 최소화하기 위해 각 점의 거릿값을 상어에서부터 탐색을 시작해 계산해 나가는 접근법을 사용하였습니다.

이 접근법으로 예제 입력1을 그래프 내 노드별 안전거리를 구하면 아래 그림 1 과 같습니다.

 

그림 1.  입력 예제1의 탐색 전후 비교

🔥 풀이과정

풀이과정은 다음과 같습니다.

 

1)  주어진 그래프 내 아기상어가 위치한 노드의 좌표값을 큐에 삽입합니다.

2)  큐가 빌 때까지 노드별 좌표 데이터를 pop 합니다. 큐가 비었다면 바로 6) 절차로 넘어갑니다.

3)  해당 좌표로부터 상하좌우, 모든 대각 방향으로 1칸씩 차례로 이동한 좌표를 계산합니다.

4)  새로운 좌표가 맵을 벗어났는지 확인합니다.

    4-1) 맵을 벗어난 경우

        - 다시 위의 3) 절차를 수행합니다.

    4-2) 맵을 벗어나지 않은 경우

        -  다음 절차를 수행합니다.

5)  새로운 좌표가 아직 탐색하지 않은 노드이거나 아기상어가 존재하지 않는 노드인지 확인합니다.

    5-1)  위 조건을 만족하는 경우

        -  새로운 좌표의 거릿값은 출발 노드의 거릿값에 1을 더한 값을 할당합니다.

        -  새로운 좌표값을 큐에 삽입합니다. 해당 좌표의 노드에서부터 재탐색하기 위함입니다.

    5-2) 위 조건을 만족하지 않는 경우

        -  다시 위의 2) 절차를 수행합니다.

6) 그래프 내 1차원 원소 중 최댓값을 출력합니다✔️

✔️ map 함수와 max 함수를 적절하게 활용할 필요가 있습니다(Conf. 코드 및 아래 느낀 점).

💻 코드

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 8가지 이동방향
d = [(-1, 0), (1, 0), (0, -1), (0, 1), 
     (-1, -1), (1, -1), (-1, 1), (1, 1)]
q = deque()

def bfs():
    while q:
        x, y = q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            # 맵에서 벗어나는 경우
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            
            # 상어가 없는 지점 or 미탐색 지점인지 확인
            if not graph[nx][ny]:
                # 새로운 지점의 거리 정보 업데이트
                graph[nx][ny] = graph[x][y] + 1
                # 새로운 지점의 좌표를 큐에 삽입
                q.append((nx, ny))

# 상어의 위치에서부터 탐색 시작
for i in range(n):
    for j in range(m):
        # 상어 위치일 경우
        if graph[i][j]:
            # 상어 위치를 큐에 삽입
            q.append((i, j))

bfs()

# 정답 출력
print(max(map(max, graph))-1)

💡 느낀 점

✅  역발상의 중요성

좌표별 최소 거릿값을 구하는 문제이지만 좌표가 아닌 상어에서부터

탐색을 시작하여 계산해 나가는 '역발상'의 중요성을 느낄 수 있었습니다.

다시 한 번 문제해결능력을 기르기 위해 다양한 문제와 접근법을 많이 접하고 활용할 필요성을 느꼈습니다.

✅  디테일의 중요성: map 함수 활용

문제의 정답은 그래프 내 노드의 최댓값입니다. 당연히 max 함수를 사용해서 최댓값을 구하려 했습니다.

그래프는 이중 리스트 구조이기 때문에 max 함수를 2번 사용하면 될 거라는 안이한 생각을 했습니다.

오답을 출력할 때마다 알고리즘 구현이 잘못된줄 알았지만, 정작 문제는 정답 출력 과정에 있었습니다😅

 

이중 리스트 내 1차원 노드의 최댓값은 max 함수만 2번 사용할 것이 아닌,

map 함수와 max 함수를 함께 사용해야 한다는 점을 깨달았습니다💡

덕분에 알고리즘 구현에 문제가 있는줄 착각하고 수차례 풀이를 검토할 수 있어서 좋았지만,

왜 기본기와 꼼꼼함이 중요한지 몸소 경험할 수 있었습니다👍

 

아래는 직접 max 함수를 활용해 이중 리스트 내 최댓값을 구하는 과정을 테스트한 것입니다.

⛏ 이중 리스트에서의 max 함수 활용

heytech = [
    [1, 2], 
    [2, 3],
    [3, 4],
    [4, 5],
    [5, 100]
]

위와 같은 이중 리스트가 있다고 가정해 보죠.

print(f"max 1번 사용: {max(heytech)}")
print(f"max 2번 사용: {max(max(heytech))}")
print(f"map 함수 활용: {max(map(max, heytech))}")

해당 리스트에 max 함수 1회, 2회, map 함께 사용한 결과를 출력하면 아래와 같습니다.

max 1번 사용: [5, 100]
max 2번 사용: 100
map 함수 활용: 100

위(⬆) 결과에서 알 수 있듯이, 이중 리스트를 max 함수에 1회 입력할 경우

각 1차원 리스트 맨 앞 원소를 기준으로 최댓값을 포함하는 리스트를 반환합니다.

따라서 단순히 max 함수를 2회 수행하면 1차원 리스트 중 [0] 인덱스를 기준으로 최댓값을 출력하게 되는 것이죠.

 

2차원 리스트 내 모든 1차원 원소의 최댓값을 구하기 위해서는 map 함수를 사용하면 효과적입니다.

map 함수에 max 함수와 이중 리스트를 입력해 주면,

1차원 리스트들 중에서 인덱스 고려없이 최댓값을 포함하는 리스트를 반환합니다.
이제 반환값을 다시 한번 max 함수에 입력해 주면 최종적으로 원소의 최댓값을 구할 수 있습니다.

참고할 만한 포스팅

이론 자료
1.  [알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)
2.  [알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)
3.  [파이썬] map 함수에 대해 알아보자(Feat. lambda 표현식)
4.  [자료구조] 큐(Queue)에 대해 알아보자(+ Python)

관련 문제
1.  BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이
2.  BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이
3.  DFS 알고리즘 #프로그래머스 #타겟넘버 | 파이썬 풀이
4.  BFS알고리즘 #프로그래머스 #가장 먼 노드 | 파이썬 풀이

---

전형적인 BFS/DFS 알고리즘 유형인 '아기상어' 관련 문제를 풀어봤습니다.

문제 풀이 피드백이나 질문 환영합니다. 아래에 댓글 남겨주세요!👍

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.