[프로그래머스]무인도 여행

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

DFS 함수를 통해 본 문제를 해결할 것이다.

코드를 작성하기 위한 순서는 다음과 같다.

1. 퍄이썬의 최대 재귀 호출 횟수는 1000이므로 런타임 에러가 발생할 수 있다. 따라서 제한을 확장한다.

2. 문제에서 주어지는 maps가 문자열 형태이므로 이를 리스트로 다시 만들어준다.

3. DFS 함수에서의 x, y 좌표가 범위를 벗어나는 지, 그리고 해당 maps의 값이 숫자인지 확인하는 check 함수를 만들어준다.

4. check 함수 조건에 만족한다면 해당 좌표에서 상, 하, 좌, 우로 좌표를 이동시켜서 재귀호출을 진행한다.

 

import sys #1번
sys.setrecursionlimit(10**5) #과도한 숫자로 제한을 확장하면 이 역시 런타임에러가 발생할 수 있으므로 주의해야한다.

def solution(maps):
    global total
    answer = []
    maps = [list(map) for map in maps] #2번
    total = 0
    
    def check(y, x): #3번
        return x >= 0 and y >= 0 and x < len(maps[0]) and y < len(maps) and maps[y][x] != 'X'
    
    def dfs(y, x):
        global total
        maps[y][x] = 'X'
        
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        for i in range(4): #4번
            mx = x + dx[i] #x += dx[i]와 같이 작성하게 되면, x값이 누적될 수 있으므로 오류가 발생한다.
            my = y + dy[i] #y += dy[i]도 마찬가지이다.)
            if check(my, mx):
                total += int(maps[my][mx])
                dfs(my, mx)
    
    for y in range(len(maps)):
        for x in range(len(maps[0])):
            if check(y, x):
                total = int(maps[y][x]) #전역 변수 total 값을 초기화 해주어야한다.
                dfs(y, x)
                if total != 0:
                    answer.append(total)
    if len(answer) == 0:
        return [-1]
    else:
        return sorted(answer)

 

DFS 함수를 구현하는데 조금 익숙해진 것 같다.

하지만 초기에는 좌표를 상, 하, 좌, 우 이동할 때, mx = x + dx[i] 대신에 x += dx[i]를 작성하여 답이 계속 안나왔었다.

사실은 오른쪽의 코드가 조금 더 간결하게 저렇게 작성했는데, check의 조건에 적합하면 상관없지만 check 조건에 맞지 않으면 좌표 값이 되돌아가지 않고 계속 누적되서 계속 오답이 발생했던 것 같다.

+=, -= 등과 같은 연산자를 사용할 때는 전, 후 조건을 잘 파악하는 것이 중요할 듯하다.