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

무인도 여행

프로그래머스

 

• 내 풀이
  • BFS
  • bfs로 하나의 섬 돌면서 합을 tmp로 구한 후에 한번에 return

from collections import deque

def solution(maps):
    answer = []
    graph = []
    for map in maps:
        graph.append(list(map))
    
    n = len(graph)
    m = len(graph[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    def bfs(i, j):
        tmp = int(graph[i][j])
        q = deque()
        q.append((i, j))
        visited[i][j] = True
        
        while q:
            x, y = q.popleft()
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                if visited[nx][ny]:
                    continue
                if graph[nx][ny] == 'X':
                    continue
                
                visited[nx][ny] = True
                tmp += int(graph[nx][ny])
                q.append((nx, ny))
        
        return tmp
        
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'X':
                continue
            if visited[i][j]:
                continue
            visited[i][j] = True
            answer.append(bfs(i, j))
    
    return sorted(answer) if answer else [-1]

 

• 내 풀이
  • DFS
  • 재귀 제한 걸어줘야 런타임에러 안터짐
    • import sys
      sys.setrecursionlimit(10**6)

import sys
sys.setrecursionlimit(10**6)


def solution(maps):
    answer = []
    graph=[]
    for map in maps:
        graph.append(list(map))
    
    n=len(graph)
    m=len(graph[0])
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    
    def dfs(i,j):
        tmp=int(graph[i][j])
        
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]

            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if visited[nx][ny]:
                continue
            if graph[nx][ny]=='X':
                continue
                
            visited[nx][ny]=True
            tmp+=dfs(nx,ny)
        
        return tmp
        
    visited=[[False for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j]=='X':
                continue
            if visited[i][j]:
                continue
            visited[i][j]=True
            answer.append(dfs(i,j))
    
    return list(sorted(answer)) if answer else [-1]