무인도 여행

DFS 풀이 - python에는 recursion limit 이 존재해서 런타임 에러 발생 가능성 있음.

import sys
sys.setrecursionlimit(10**5)

visited = [[False for i in range(101)] for j in range(101)]

def dfs(row, col, maps):
    global visited

    tot = int(maps[row][col])
    dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
    visited[row][col] = True

    for dxx, dyy in zip(dx, dy):
        nxtRow, nxtCol = row + dxx, col + dyy
        if nxtRow < 0 or nxtRow >= len(maps) or nxtCol < 0 or nxtCol >= len(maps[0]):
            continue

        if maps[nxtRow][nxtCol] != "X" and visited[nxtRow][nxtCol] == False:
            tot += dfs(nxtRow, nxtCol, maps)

    return tot


def solution(maps):
    global visited

    answer = []
    row, col = len(maps), len(maps[0])

    # DFS 탐색
    for i in range(row):
        for j in range(col):
            if visited[i][j] == False and maps[i][j] != "X":
                answer.append(dfs(i, j, maps))

    if len(answer) == 0:
        answer.append(-1)

    answer.sort()

    return answer

BFS 풀이

from collections import deque

vis = [[False for i in range(101)] for j in range(101)]

def bfs(row, col, maps):
    global vis
    vis[row][col] = True
    
    if maps[row][col] == "X":
        return 0
    
    q = deque()
    item = int(maps[row][col])
    q.append([row, col, item])
    
    val = 0
    while(q):
        curRow, curCol, tot = q.popleft()
        vis[curRow][curCol] = True
        val += tot
        dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
        
        for dxx, dyy in zip(dx,dy):
            nxtRow, nxtCol = curRow + dxx, curCol + dyy

            if 0 <= nxtRow < len(maps) and 0 <= nxtCol < len(maps[0]):
                if maps[nxtRow][nxtCol] != "X" and vis[nxtRow][nxtCol] == False:
                    nxtItem = int(maps[nxtRow][nxtCol])
                    q.append([nxtRow, nxtCol, nxtItem])
                    vis[nxtRow][nxtCol] = True
    return val


def solution(maps):
    global vis
    
    answer = []
    row, col = len(maps), len(maps[0])
    
    # BFS
    for i in range(row):
        for j in range(col):
            if vis[i][j] == False:
                val = bfs(i,j,maps)
                if val > 0:
                    answer.append(val)
    
    if len(answer) == 0:
        answer.append(-1)
        
    answer.sort()
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges