무인도 여행(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

지도에 섬들이 존재하며 각 섬들에서 며칠씩 머물수 있는지를 구하는 문제이다. 이어진 장소는 하나의 섬으로 간주하며 탐색을 통해 칸에 적힌 수를 합해줘야한다. 이웃한 장소들을 탐색하며 수를 더해주는 방식인 BFS 를 사용하였다.

 

처리과정

1. 맵을 순회하며, 방문한 적이 없는 섬에 대해서 bfs를 실행한다
    1.1. bfs를 통해 해당 섬을 탐색하고, 해당 섬에 적힌 수들을 더해준다.
2. 각 섬들의 체류 가능 기간을 오름차순 정렬한다

 

 

 

코드

from collections import deque
dy=[-1,0,1,0]
dx=[0,1,0,-1]

# 방문하지 않는 위치를 입력받아서, 섬 내부의 모든 숫자를 더하고 결과값을 반환한다
def bfs(maps,visited,y,x):
    n,m=len(maps),len(maps[0])
    q=deque([(y,x)])
    count=0
    while q:
        cy,cx=q.popleft()
        if visited[cy][cx]!=0:
            continue
        visited[cy][cx]=1
        count+=int(maps[cy][cx])
        for i in range(len(dy)):
            ny,nx=cy+dy[i],cx+dx[i]
            if 0<=ny<n and 0<=nx<m and maps[ny][nx]!='X' and visited[ny][nx]==0:
                q.append((ny,nx))
                
    return count


def solution(maps):
    n,m=len(maps),len(maps[0])
    visited=[[0]*m for _ in range(n)]
    answer = []
    
    # 섬을 순회하며 방문하지 않는 장소에 대해 bfs를 실행한다
    for i in range(n):
        for j in range(m):
            if maps[i][j]!='X' and visited[i][j]==0:
                answer.append(bfs(maps,visited,i,j))
    
    # 체류기간을 오름차순 정렬한다
    answer.sort()
    if len(answer)==0:
        answer.append(-1)
    return answer