[코딩테스트] 프로그래머스 무인도 여행 파이썬(Python)

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

프로그래머스

import sys
def solution(maps):
    sys.setrecursionlimit(10 ** 5)
    rows = len(maps)
    columns = len(maps[0])
    visited = [[False for _ in range(columns)] for _ in range(rows)]
    global total
    total = 0
    def dfs(x, y):
        global total
        visited[x][y] = True
        dx = [1,-1, 0, 0]
        dy = [0, 0, 1, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= nx < rows and 0 <= ny < columns):
                continue
            if visited[nx][ny]:
                continue
            if maps[nx][ny] == 'X':
                continue
            total += int(maps[nx][ny])
            dfs(nx, ny) 
    result = []
    for i in range(rows):
        for j in range(columns):
            if maps[i][j] != 'X' and visited[i][j] != True:
                total = int(maps[i][j])
                dfs(i, j)

                result.append(total)
    if len(result) > 0:
        return sorted(result)
    else:
        return [-1]

먼저 재귀를 진행할때 런타임에러가 나오는 상황을 방지하기 위하여 import sys를 하고 sys.setrecursionlimit(10 **5)를 작성하였습니다.

아래의 4가지 변수를 초기화 하였습니다

• rows : 행의 수
• columns : 열의 수
• visited : 방문 여부를 확인할 2차원 리스트
• total : 무인도에서 최대 며칠동안 머물 수 있는지 저장하는 변수

또한 total 변수는 gloabl를 사용하여 전역변수로 선언하였습니다.

 

무인도를 탐색하는 dfs함수를 작성하였습니다.

먼저 global로 전역변수 total을 선언해주고 visited[x][y] = True로 하여 방문처리를 해줍니다.

그리고 상,하,좌,우로 이동할 수 있는 dx, dy를 초기화 해줍니다.

반복문을 사용하여 상,하,좌,우로 이동하는데

다음의 조건을 통과하는 경우에만 total에 값을 더하고 재귀함수를 호출 할 수 있도록 합니다.

• 조건1(if not (0 <= nx < rows and 0 <= ny < columns)) : 범위를 벗어나는 경우는 무시합니다.
• 조건2(visited[nx][ny]) : 이미 방문처리가 된 곳은 무시합니다.
• 조건3(maps[nx][ny] == 'X') : 지도상 'X'로 처리된 곳은 무시합니다.

dfs 함수를 빠져나오고 solution 함수로 돌아오겠습니다.

2중반복문을 사용하는데 현재 좌표가 'X'가 아니고 방문처리가 되어있지 않은 좌표만 탐색하고 좌표에 해당하는 값을 초기 total로 설정하고 dfs함수를 실행합니다.

나온 결과 total를 result에 저장해주고 result의 길이가 0보다 크다면 정렬을 하여 반환해주고 그렇지 않다면 섬이 존재하지 않기 때문에 [-1]을 반환합니다.