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

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

프로그래머스

 

 

✅ DFS 풀이

import sys

sys.setrecursionlimit(10**6)

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, graph):
    count = graph[x][y]  # 현재 위치 식량값
    graph[x][y] = 0  # 방문 처리

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]

       
        if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and graph[nx][ny] > 0:
            count += dfs(nx, ny, graph)

    return count

def solution(maps):
    graph = []

    for m in maps:
        m = m.replace('X', '0')
        graph.append(list(map(int, list(m))))

    answer = []

    for x in range(len(graph)):
        for y in range(len(graph[0])):
            if graph[x][y] > 0:  # 아직 방문하지 않음
                count = dfs(x, y, graph)
                answer.append(count)

    if answer:
        return sorted(answer)
    else:
        return [-1]

이 문제와 같이 그룹핑을 해야하는 경우엔, 가지를 끝까지 파고드는 DFS 방식이 적합하다고 생각하였다.

하지만, 모든 테스트케이스에 대해 통과하지 못해 재귀깊이를 늘려주니 통과할 수 있었다.

 

 

✅ BFS 풀이

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, graph):
    queue = deque([(x, y)])
    count = 0
    
    while queue:
        x, y = queue.popleft()
        
        if graph[x][y] == 0:
            continue
        
        count += graph[x][y]
        graph[x][y] = 0  # 방문 처리
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and graph[nx][ny] > 0:
                queue.append((nx, ny))
    
    return count

def solution(maps):
    graph = []
    for m in maps:
        m = m.replace('X', '0')
        graph.append(list(map(int, list(m))))
    
    answer = []
    
    for x in range(len(graph)):
        for y in range(len(graph[0])):
            if graph[x][y] > 0:  # 아직 방문하지 않은 경우
                count = bfs(x, y, graph)
                answer.append(count)
    
    if answer:
        return sorted(answer)
    else:
        return [-1]