[프로그래머스] - Lv2 무인도 여행(python)

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

프로그래머스

 

📌 - 무인도 여행 - 접근

 

이 문제는 map의 크기도 100으로 제한되어 있고, 

상,하,좌,우를 이용하면서 해당하는 경로의 숫자를 전부 더해주는 방식이라 DFS, BFS 문제라고 생각했고

 

백준의 안전 영역이나 빙산 문제와 비슷하다고 생각해서 BFS로 풀었다.

 

1. 0,0부터 N,M까지 전부 탐색하면서 방문체크
2. 방문하지 않은 섬일때 BFS를 이용해서 인접한 섬들의 수를 더해주고 다시 방문체크
3. 인접한 섬들을 모두 체크 한뒤 다시 반복문으로 방문하지 않은 섬들을 다시 체크

이렇게 반복해서 나온 수들을 answer배열에 넣어주고 정렬해서 출력하면 답이 나오게 된다

 

📌 -  python으로 푼 코드

from collections import deque


def BFS(start,end,visited,island):
    q = deque()
    q.append((start,end))
    visited[start][end] = True
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    result = int(island[start][end])
    while q :
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=ny< len(island[0]) and 0<=nx<len(island) and not visited[nx][ny] and island[nx][ny] !='X':
                visited[nx][ny] = True
                q.append((nx,ny))
                result += int(island[nx][ny])
                
                
    return result
                
        
    

def solution(maps):
    
    answer = []
    island = [list(map(str,maps[i])) for i in range(len(maps))]
    visited = [[False] * len(island[0]) for _ in range(len(island))]
    

    
    for i in range(len(island)):
        for j in range(len(island[0])):
            if island[i][j] != 'X' and not visited[i][j]:
                answer.append(BFS(i,j,visited,island))
    
    if answer:
        answer.sort()
    else:
        answer.append(-1)
    
                
    return answer