[Level 2] 무인도 여행(Python)

프로그래머스

문제

지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있다. 
지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타낸다. 
- 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룬다.
- 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다.
지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수 완성하라.
만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해라.

 

<제한 사항>
- 3 ≤ maps의 길이 ≤ 100
    - 3 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열
- 지도는 직사각형 형태

 

풀이 과정

풀이 시간: 15분

알고리즘: BFS 또는 DFS

각 칸에 대해서 상하좌우로 이동가능한지 BFS 또는 DFS를 통해 탐색하면서 각 섬에 최대로 머무를 수 있는 기간을 구하면 된다.

시간 복잡도: O(NlogN)

- 모든 칸을 한 번씩 확인: O(rows * cols)
- 각 DFS 또는 BFS 호출: O(rows * cols)
- 결과 정렬: O(NlogN)
-> O(rows * cols) + O(rows * cols) + O(NlogN)

 

코드

BFS로 작성한 코드

from collections import deque


def bfs(x: int, y: int, visited: set, maps: list) -> int:
    """
    :param x: 현재 확인하고 있는 칸의 x좌표
    :param y: 현재 확인하고 있는 칸의 y좌표
    :param visited: 방문처리를 위한 set
    :param maps: 지도를 나타내는 문자열 배열
    :return: (x,y)좌표 섬에서 최대 머무를 수 있는 날짜
    """
    q = deque([(x, y)])
    # 1. 시작점 방문처리
    visited.add((x, y))
    total_food = int(maps[x][y])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # 2. 각 칸에서 상하좌우로 이동(큐가 빌 때까지)
    while q:
        cx, cy = q.popleft()
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            # 1) 이웃한 칸이 범위를 벗어나지 않았는지, 2) 아직 방문하지 않은 칸, 3) 'X'(바다)가 아니라면 탐색
            if (0 <= nx < len(maps) and 0 <= ny < len(maps[0])) and (nx, ny) not in visited and maps[nx][ny] != 'X':
                q.append((nx, ny))
                visited.add((nx, ny))
                total_food += int(maps[nx][ny])
                
    return total_food


def solution(maps: list) -> list:
    """
    :param maps: 지도를 나타내는 문자열 배열
    :return: 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 정렬한 리스트
    """
    answer = [] # 각 섬에서 최대 며칠씩 머무를 수 있는지
    rows, cols = len(maps), len(maps[0])
    visited = set() # 방문처리를 위한 set
    
    for i in range(rows):
        for j in range(cols):
            # 칸이 'X'가 아니면서 아직 방문하지 않은 칸이라면 탐색
            if maps[i][j] != 'X' and (i, j) not in visited:
                answer.append(bfs(i, j, visited, maps))

    return sorted(answer) if answer else [-1]

 

DFS로 작성한 코드

def dfs(x: int, y: int, visited: list, maps: list,) -> int:
    """
    :param x: 현재 확인하고 있는 칸의 x좌표
    :param y: 현재 확인하고 있는 칸의 y좌표
    :param visited: 방문처리를 위한 set
    :param maps: 지도를 나타내는 문자열 배열
    :return: (x,y)좌표 섬에서 최대 머무를 수 있는 날짜
    """
    stack = [(x, y)]
    visited[x][y] = True
    total_food = 0

    while stack:
        cx, cy = stack.pop()
        total_food += int(maps[cx][cy])

        # 아직 방문하지 않은 칸 중 이동가능하다면 스택에 추가
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]) and maps[nx][ny] != 'X' and not visited[nx][ny]:
                stack.append((nx, ny))
                visited[nx][ny] = True

    return total_food


def solution(maps: list) -> list:
    """
    :param maps: 지도를 나타내는 문자열 배열
    :return: 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 정렬한 리스트
    """
    rows, cols = len(maps), len(maps[0])
    visited = [[False] * cols for _ in range(rows)] # 방문처리를 위한 2차원 배열
    answer = []

    for i in range(rows):
        for j in range(cols):
            if maps[i][j] != 'X' and not visited[i][j]:
                answer.append(dfs(i, j, visited, maps))

    return sorted(answer) if answer else [-1]

 

기본적인 그래프 탐색(BFS, DFS) 문제여서 풀이가 어렵지 않았다.

위 문제를 풀면서 BFS와 DFS 코드(스택 방식) 둘 다 작성해봤는데

DFS의 경우, 재귀 방식으로 구현한다면 파이썬 재귀 깊이의 기본값이 1000이기 때문에 대부분 재귀 깊이를 sys모듈(sys.setrecursionlimit)을 통해 늘려줘야 한다. (안그러면 높은 확률로 RecursionError가 발생해 코드 제출시 시간 초과가 난다.)

 

하지만, 개인적으로 sys 모듈을 통해 재귀 깊이를 변경하는 방식을 좋아하지 않는다.

그 이유는, 재귀 깊이 제한 자체가 무한 재귀로 인해 C 스택의 오버플로가 발생하고 파이썬이 충돌하는 것을 방지하기 위한 것인데 임의로 인터프리터 환경을 바꾸는 방식은 좋은 방식이 아니라고 생각하기 때문이다. (실제로, 삼성 코딩테스트는 sys모듈을 사용할 수 없다.)

따라서 위 코드처럼, DFS를 스택 방식으로 구현했다. 이렇게 스택 방식으로 구현하면 재귀 깊이 제한을 변경해주지 않아도 BFS와 비슷한 실행 시간을 갖는다.

 

아래는 이전에 풀었던 다른 플랫폼의 유사한 문제들이다.

- https://www.acmicpc.net/problem/2667

- https://softeer.ai/practice/6282