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

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

프로그래머스

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

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

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

 

아직 접근방식을 잘 모르겠다... 우선 섬의 지도부터 만들어보자.

def solution(maps):
    answer = []
    island = {}
    cols_num = len(maps)
    rows_num = len(maps[0])
    
    for col in range(cols_num):
        island.update({col:[]})
    
    
    return island

 

섬의 범위만큼의 딕셔너리를 만들었다. 이제 다음 목표는 식량의 위치를 모두 순회하는 것이다.

 

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]:
                print(col, row)

 

이번에는 각 섬들을 순회하면서 X가 아닌 좌표(섬의 좌표)를 확인해주었다. 다음에는 각 섬들의 식량의 갯수를 더해주자.

 

def food(maps, col, row, island, sum_food):
    sum_food += int(maps[col][row])
    island[col].append(row)
    return sum_food, island

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)
                print(sum_food)

 

food함수는 지도, 가로, 세로, 방문한 섬, 식량 합계를 받아서 식량의 총 합계와 방문한 섬을 출력하는 함수이다. 즉 방문한 섬을 기록하고 그곳에 있는 식량의 갯수를 더해간 것이다. 지금은 모든 섬들의 식량을 더하고 있지만 다음 과정에서 연결된 섬들만 출력할 예정이다.

 

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

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

 

food 함수의 각 조건문은 위에서부터 다음과 같다.

1. 현재 섬의 북쪽을 탐색하는 조건문, 현재 섬이 가장 북쪽일때, 북쪽이 바다일때, 이미 방문한 섬일때는 실행되지 않는다.

2. 현재 섬의 남쪽을 탐색하는 조건문, 현재 섬이 가장 남쪽일때, 남쪽이 바다일때, 이미 방문한 섬일때는 실행되지 않는다.

3. 현재 섬의 서쪽을 탐색하는 조건문, 현재 섬이 가장 서쪽일때, 서쪽이 바다일때, 이미 방문한 섬일때는 실행되지 않는다.

4. 현재 섬의 동쪽을 탐색하는 조건문, 현재 섬이 가장 동쪽일때, 동쪽이 바다일때, 이미 방문한 섬일때는 실행되지 않는다.

각 조건문들은 재귀함수를 통해서 반복되며 sum_food에 모든 연결된 섬들의 식량의 합계를 저장하고 방문한 섬은 island에 저장해서 중복을 방지한다.. 즉 해당 함수가 종료될 경우 모든 연결된 섬을 방문했다는 의미가 된다.

 

solution의 반복문에 경우 food함수의 반환값을 answer에 저장하고 있다. 저장 후, 현재의 섬과 다른 섬을 구분하기 위해 sum_food를 0으로 초기화한다.

 

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

 

마지막으로 answer의 입력값이 없을 경우 -1을 반환하고 값이 있을 경우 오름차순 정렬해서 값을 반환하면 된다.

 

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

런타임에러?

 

테스트 케이스는 통과했지만 실행을 해보니 에러가 발생했다.

일단 출력에 성공한 값은 모두 통과했고 다른 오류가 발생한 것은 아닌걸 보아서 코드자체에 문제가 있는 것은 아닌것같다. 검색을 통해 알아본 결과 재귀함수의 경우 재귀한도라는 것이 존재한다고 한다. 재귀함수가 일정 횟수이상 반복되면 무한루프를 방지하기 위해서 강제로 종료되고 에러가 발생하는 것으로 기본적으로 1000으로 설정되어있다.

import sys
sys.setrecursionlimit(1500)

성공률이 높아졌다.

 

시험삼아서 가장 위에 재귀한도를 늘려주는 코드를 추가했더니 성공률이 올라갔다. 재귀한도의 문제가 맞았던것같다.

 

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

성공!

 

재귀한도를 500단위로 늘리면서 테스트해본 결과 3500에서 성공할 수 있었다.

 

이번 문제는 사실 인터넷 검색을 아주 많이 해서 겨우 풀어낸 문제이다. 당연히 그대로 복사붙여넣기 한 것이 아니라 vs코드에서 디버그모드로 여러번 반복해서 실행해보면서 코드의 작동원리를 파악하고 최대한 비슷하게 구현할 수 있도록 해본 것이다. 재귀함수를 자주 사용해보지 않아서 실행순서가 아주 어색했었다.

재귀함수의 어려움이라고 하면 내가 지정한 변수가 함수를 거치면서 어떤값으로 바뀌어서 반환이 될지 잘 모르겠다는 점이다. 이번주 후반기부터 캠프의 알고리즘주차가 시작되는데 해당강의를 수강하면 익힐 수 있을까? 아직 잘 모르겠다.