프로그래머스 - 무인도 여행

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

문제 설명
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

 

섬의 예시

 

오랜만에 제대로 풀어보는 코딩테스트 문제, 워밍업을 겸해서 이전에 풀었던 문제 중 그때는 어려워했지만 지금은 풀어볼만한 문제를 가져왔다.

 

https://youtharchive.tistory.com/67

알고리즘 코드카타 111 - 무인도 여행

이전에 풀었던 문제의 블로그 링크

 

 

문제를 보니 bfs탐색을 사용해서 풀어낼 수 있을 것같다는 생각이 들었다.

 

def solution(maps):
    answer = []
    w = len(maps[0])
    h = len(maps)
    maps_list = [list(row) for row in maps]

    for i in range(h):
        for j in range(w):
            print(j, i)

 

가장 먼저 한 것은 지도의 모든 부분을 순회하는 반복문을 작성하는 것이다. for반복문 두개를 중첩하여 모든 구간을 탐색할 수 있도록 했다.

 

# def solution(maps):
#     answer = []
#     w = len(maps[0])
#     h = len(maps)

#     for i in range(h):
#         for j in range(w):
            if list[i][j] == "X":
                continue
            else:
                bfs(j, i, list)

다음으로는 식량이 있는 곳과 없는 곳을 구분하는 반복문을 추가하고 식량이 존재할 경우에 bfs 탐색을 실행하도록 한다. (bfs함수에서 아직 어떤 값을 반환할지 결정하지 못했기 때문에 우선 비워두었다.)

 

from collections import deque


def bfs(w, h, maps):
    explore = deque()
    explore.append((w, h))
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    food = int(maps[h][w])
    maps[h][w] = "X"

 

queue를 사용하기 위해 deque를 임포트 해준다. (리스트를 사용해도 상관없지만 나는 속도를 고려해서 큐를 사용했다.)

탐색할 지점에 대한 정보를 저장하는 explore 큐를 생성하고 시작지점의 위치를 추가한다. 그리고 현재 위치를 기준으로 4방향에 대해서 탐색을 할 것이므로 방향을 나타내는 durection을 지정해준다 순서대로 오른쪽, 왼쪽, 아래쪽, 위쪽을 나타낸다.

이제 현재 위치의 식량을 food에 입력하고 식량을 회수했으므로 현재 위치의 식량을 "X"로 표시하여 삭제해준다.

 

# def bfs(w, h, maps):
#     explore = deque()
#     explore.append((w, h))
#     direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
#     food = int(maps[h][w])
#     maps[h][w] = "X"

    while explore:
        x, y = explore.popleft()

        for d in direction:
            dx, dy = d

            if (
                0 <= x + dx < len(maps[0])
                and 0 <= y + dy < len(maps)
                and maps[y + dy][x + dx] != "X"
            ):
                explore.append((x + dx, y + dy))
                food += int(maps[y + dy][x + dx])
                maps[y + dy][x + dx] = "X"

    return food

explore에 저장한 좌표를 순서대로 탐색하고 탐색할 공간이 없을 경우 탐색을 종료한다. 탐색할 좌표의 위치를 popleft로 꺼내서 중복탐색을 방지할 수 있다.

각 방향을 d라고 하고 현재 좌표인 x, y를 각각 dx, dy만큼 움직인 좌표가 지도 안에 있으면서 동시에 식량이 존재할 경우 탐색할 좌표로 추가하고 현재 위치의 식량을 food에 더해준 뒤 해당 위치의 식량은 방금 회수 했으므로 "X"로 삭제해준다.

위의 반복문이 실행되며 탐색중인 좌표와 인접한 좌표의 식량이 모두 food에 더해지게 되고 회수한 식량들은 maps에서 삭제하게 된다.

 

# def solution(maps):
#     answer = []
#     w = len(maps[0])
#     h = len(maps)
    maps_list = [list(row) for row in maps]

#     for i in range(h):
#         for j in range(w):
#             if maps_list[i][j] == "X":
#                 continue
#             else:
                food = bfs(j, i, maps_list)
                answer.append(food)

 

다시 silution으로 돌아와서 작성한 bfs에서 특정 요소를 "X"로 간단하게 수정하기 위해 maps를 리스트로 변경해준다. 그리고 식량이 존재할 경우 bfs탐색을 통해 인접한 모든 섬들의 식량의 갯수를 반환하여 answer에 입력하게 된다.

반복문을 통해 지도의 모든 좌표에 대해 탐색을 하게 된다.

 

# def solution(maps):
#     answer = []
#     w = len(maps[0])
#     h = len(maps)
#     maps_list = [list(row) for row in maps]

#     for i in range(h):
#         for j in range(w):
#             if maps_list[i][j] == "X":
#                 continue
#             else:
#                 food = bfs(j, i, maps_list)
#                 answer.append(food)

    if not answer:
        return [-1]
    else:
        answer.sort()
        return answer

 

마지막으로 회수한 식량이 하나도 없을 경우 -1을 반환하고 그렇지 않을 경우 오름차순 정렬해서 반환하면 문제를 해결할 수 있다.

 

from collections import deque


def bfs(w, h, maps):
    explore = deque()
    explore.append((w, h))
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    food = int(maps[h][w])
    maps[h][w] = "X"

    while explore:
        x, y = explore.popleft()

        for d in direction:
            dx, dy = d

            if (
                0 <= x + dx < len(maps[0])
                and 0 <= y + dy < len(maps)
                and maps[y + dy][x + dx] != "X"
            ):
                explore.append((x + dx, y + dy))
                food += int(maps[y + dy][x + dx])
                maps[y + dy][x + dx] = "X"

    return food


def solution(maps):
    answer = []
    w = len(maps[0])
    h = len(maps)
    maps_list = [list(row) for row in maps]

    for i in range(h):
        for j in range(w):
            if maps_list[i][j] == "X":
                continue
            else:
                food = bfs(j, i, maps_list)
                answer.append(food)

    if not answer:
        return [-1]
    else:
        answer.sort()
        return answer

전체 코드

 

import sys
sys.setrecursionlimit(3500)

def food(maps, col, row, island, sum_food):
    sum_food += int(maps[col][row])
    island[col].append(row)
    if col != 0 and maps[col-1][row] != 'X' and row not in island[col-1]:
        sum_food, island = food(maps, col-1, row, island, sum_food)
    if col != len(maps)-1 and maps[col+1][row] != 'X' and row not in island[col+1]:
        sum_food, island = food(maps, col+1, row, island, sum_food)
    if row != 0 and maps[col][row-1] != 'X' and row-1 not in island[col]:
        sum_food, island = food(maps, col, row-1, island, sum_food)
    if row != len(maps[0])-1 and maps[col][row+1] != 'X' and row+1 not in island[col]:
        sum_food, island = food(maps, col, row+1, island, sum_food)
    return sum_food, island
    

def solution(maps):
    answer = []
    island = {}
    sum_food = 0
    cols_num = len(maps)
    rows_num = len(maps[0])
    
    for col in range(cols_num):
        island.update({col:[]})
    for col in range(cols_num):
        for row in range(rows_num):
            if maps[col][row] != 'X' and row not in island[col]:
                sum_food, island = food(maps, col, row, island, sum_food)
                answer.append(sum_food)
                sum_food = 0
    if not answer:
        answer = [-1]
    else:
        answer.sort()
    return answer

이전 코드

 

이전에는 재귀함수를 이용해서 풀었었는데 bfs를 이용하는 것이 코드 가독성, 유지보수 측면에서 더 낫다고 생각한다.