[Python] 무인도 여행

 

 

문제링크 및 설명

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

프로그래머스

 

접근법

• DFS를 활용하여 이어진 섬들끼리의 총 합을 answer에 append하는 방식으로 구현하였다.
• DFS에서 0이 리턴되는 경우는 방문할 수 없는 섬이라 answer에 append하지 않는다.
• 런타임 에러가 발생하여 sys.setrecursionlimit을 활용하여 재귀 최대 깊이를 설정하였다. 

import sys
sys.setrecursionlimit(int(1e9))

mx = [1, 0, -1, 0]
my = [0, -1, 0, 1]

def dfs(x, y, map, visited):
    global n
    global m
    
    if x >= n or x < 0 or y >= m or y < 0:
        return 0 
    if visited[x][y] == 1:
        return 0 
    if map[x][y] == "X":
        return 0 
    
    visited[x][y] = 1
    sum = int(map[x][y])
    
    for i in range(4):
        nx, ny = x + mx[i], y + my[i]
        sum += dfs(nx, ny, map, visited)

    return sum
    
        
    
def solution(maps):
    answer = []
    
    # input
    global n # 행
    global m # 열
    
    n = len(maps)
    m = len(maps[0])
    map = [[0 for _ in range(m)] for _ in range(n)]
    visited = [[0 for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        for j in range(len(maps[i])):
            map[i][j] = maps[i][j]

    for i in range(n):
        for j in range(len(maps[i])):
            if map[i][j] == "X":
                continue
            else:
                sum = dfs(i, j, map, visited)
                if sum != 0:
                    answer.append(sum)
    
    if len(answer) == 0:
        return [-1]
    else: 
        return sorted(answer)

---

처음 생각했던 알고리즘의 문제점(틀린이유)

1. sum을 반환하여 solution 함수로 리턴하려 하였지만, dfs 함수 내에서 return 되면서 sum의 값이 변경되어 원하는 값이 solution 함수에 리턴되지 않는 현상이 발생하였다.

이를 해결하기 위해 dfs 함수의 반환값들을 받아 (dfs내 sum 변수에) 합계를 저장하고, 이를 solution 함수로 반환하도록 수정하여 해결하였다.

 

2. answer에 방문할 수 없는 섬들의 값들이 0으로 저장되어 있었다. 이를 제거하기 위해 list.remove(x)를 활용하였지만, list.remove는 0이 여러개 있을 때 첫 0만 제거하기 때문에 틀린 닶을 반환하는 현상이 발생하였다.

이를 해결하기 위해 answer 값을 append할 때 0인지 확인하는 코드를 추가하여 해결하였다.

import sys
sys.setrecursionlimit(int(1e9))

mx = [1, 0, -1, 0]
my = [0, -1, 0, 1]

def dfs(x, y, map, visited, sum):
    global n
    global m
    
    if x >= n or x < 0 or y >= m or y < 0:
        return
    if visited[x][y] == 1:
        return
    if map[x][y] == "X":
        return
    
    visited[x][y] = 1
    sum += int(map[x][y])
    for i in range(4):
        nx, ny = x + mx[i], y + my[i]
        dfs(nx, ny, map, visited, sum)

    return sum
    """
    DFS는 재귀로 호출되기 때문에 여기서 위와 같은 방식으로 리턴하게 되면 이전에 호출된 DFS함수 내에 리턴되게 된다. 
    따라서 원하는 값을 solution함수로 리턴할 수 없게 된다.
    """
        
    
def solution(maps):
    answer = []
    
    # input
    global n # 행
    global m # 열
    
    n = len(maps)
    m = len(maps[0])
    map = [[0 for _ in range(m)] for _ in range(n)]
    visited = [[0 for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        for j in range(len(maps[i])):
            map[i][j] = maps[i][j]

    for i in range(n):
        for j in range(len(maps[i])):
            if map[i][j] == "X":
                continue
            else:
                sum = dfs(i, j, map, visited, 0)
                answer.append(sum)
    
    if len(answer) == 0:
        return [-1]
    else:
    	answer.remove(0)
        return sorted(answer)

 

사용된 알고리즘

DFS