[프로그래머스/python] Level2 - 무인도

 💬 문제

 

 

 

 

🔨 입출력

 

 

💡 해결

문제를 보고 기본적인 탐색 문제라서 다시 한번 되짚어 본다는 느낌으로 풀었다.

최단 거리를 묻지 않고 기본 탐색 이기 때문에 DFS를 한번 써볼려고 했다. 

map에 있는 자료들을 arr로 옮겨놓고 원래는 "X"로 되어 있는 공간을 arr에 0으로 채워주었다.

그런데 이걸 깜빡하고 나중에 조건에서 arr != "X"라고 하여 꽤 시간을 뺐겼다..

 

뭐 이정도는 금방 풀었는데 중요한건 프로그래머스 환경에서 제출시 런타임 에러가 나는 것이었다.

내가 잘못 푼 줄 알고 코드를 고치다가 단톡방에 물어봤는데.. sys.setrecursionlimit을 사용하여 재귀횟수에 제한을 걸라는 것이었다.

 

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

 

이게 뭐람.. 백준만 푼 나에겐 진짜 처음본 코드다

대부분 코테가 프로그래머스 환경에서 실행된다는걸 감안하면 굉장히 중요한 발견이라고 할 수 있겠다.

파이썬의 기본 재귀 깊이는 1000으로 상당히 낮은 수위에 해당하는데, 그 이상을 넘어가면 런타임 에러가 걸리는 것이었다.

앞으로, 모든 재귀를 쓰는 문제에서는 이 코드를 바르고 해야지..!

👨🏻‍💻  CODE
 

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

def DFS(arr,visited,x,y,cnt):
        
    visited[x][y] = True
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
        
    for i in range(4):
        nx = x+ dx[i]
        ny = y+ dy[i]
        if 0<=nx<len(visited) and 0<=ny<len(visited[0]) and not visited[nx][ny] and arr[nx][ny] !=0:
            cnt[0] += arr[nx][ny]
            DFS(arr,visited,nx,ny,cnt)
        

    
def solution(maps):
    col = len(maps)
    row = len(maps[0])
    arr = [[0 for i in range(row)] for j in range(col)]
    visited = [[False for i in range(row)] for j in range(col)]
    answer = [] 
    
    for i in range(col):
        for j in range(row):
            if maps[i][j] != "X":
                arr[i][j] = int(maps[i][j])
                
        
    for i in range(col):
        for j in range(row):
            if not visited[i][j] and arr[i][j] != 0:
                cnt = []
                cnt.append(arr[i][j])
                DFS(arr,visited,i,j,cnt)
                answer.append(cnt[0])
    
    answer.sort()
    if not answer: answer.append(-1)

    return answer

 

 

💪🏻 결과