📗 무인도 여행

프로그래머스

첫 번째 접근: dfs

import sys; sys.setrecursionlimit(10000)

def solution(maps):
    answer = []
    dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
    
    def dfs(x, y):
        visited[x][y] = True
        foods = int(maps[x][y])
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (0 <= nx < len(maps)) and (0 <= ny < len(maps[0])):
                if maps[nx][ny] != 'X' and not visited[nx][ny]:
                    foods += dfs(nx, ny)
        
        return foods

    visited = [[False] * len(maps[0]) for _ in range(len(maps))]
    
    for x in range(len(maps)):
        for y in range(len(maps[0])):
            if maps[x][y] != 'X' and not visited[x][y]:
                answer.append(dfs(x, y))
            
    return [-1] if not answer else sorted(answer)

• 우선 탐색 유형의 가장 기본이 되는 문제 중 하나였던 것 같습니다.

왜 이렇게 풀었을까?

• 백준 문제에도 유사한 문제들이 몇몇 있습니다. 이어진 섬의 개수를 찾는다든지, 크기가 가장 넓은 그림을 찾는다든지 등의 문제들인데, 이 문제들 모두 우선 탐색 유형으로 접근해서 푼 기억이 있었기에 '무인도 여행' 문제 또한 우선 탐색으로 접근해보았습니다.
• 먼저는 maps의 크기가 그리 크지 않았기 때문에 dfs로도 충분히 풀 수 있다고 생각하여 dfs로 먼저 풀어보는 시도를 하게 되었습니다.
• 문제를 푸는 데 있어서는 foods를 초기화하고, 재귀를 이용하여 foods를 누적시켜나가는 과정만 추가해준다면 dfs 기본 구조와 그리 차이가 나지 않습니다.
• 재귀 제한은 기본으로 뒀을 경우에는 런타임 에러가 발생하여, 재귀 깊이를 10000으로 적당히 설정하였습니다.

---

두 번째 접근: bfs

from collections import deque

def solution(maps):
    answer = []
    dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
    
    def bfs(x, y):
        queue = deque([(x, y)])
        visited[x][y] = True
        foods = 0
        
        while queue:
            x, y = queue.popleft()
            foods += int(maps[x][y])
            
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < len(maps)) and (0 <= ny < len(maps[0])):
                    if maps[nx][ny] != 'X' and not visited[nx][ny]:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                        
        return foods

    visited = [[False] * len(maps[0]) for _ in range(len(maps))]
    
    for x in range(len(maps)):
        for y in range(len(maps[0])):
            if maps[x][y] != 'X' and not visited[x][y]:
                answer.append(bfs(x, y))
            
    return [-1] if not answer else sorted(answer)

왜 이렇게 풀었을까?

• 이 문제에서는 dfs와 bfs의 실행 시간 차이가 크진 않았지만, maps의 크기가 문제의 조건보다 훨씬 커지는 경우에는 bfs로 푸는 것이 더 효율적이라고 생각합니다.