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

 

 

 

프로그래머스

 

 

풀이

 

연결된 땅들의 크기를 계산하여 각 섬의 크기를 오름차순으로 출력하는 문제이다.

DFS 및 BFS를 사용하여 해결할 수 있다.

 

작성된 코드의 알고리즘 순서는 다음과 같다.

 

1. 맵을 탐색하며 X가 아닌 부분(섬의 일부)을 찾는다.
2. 섬의 일부를 발견한 경우, BFS로 섬 전체를 탐색한다.
   
   1. 섬을 방문한 좌표의 경우 X로 표시로 체크하여 재방문을 막는다.
3. 섬 탐색이 끝나면 현재 섬의 크기를 저장한 다음, 맵을 이어서 탐색하며 다른 섬들을 찾는다.
4. 맵 탐색이 전부 끝나면, 저장된 섬의 크기를 오름차순 정렬한 다음 반환한다.

 

def solution(maps):
    board = [list(m) for m in maps]
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    N, M = len(board), len(board[0])
    res = []
    
    # 맵 탐색
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'X':
                continue
            
            # 섬의 일부를 발견했으므로 섬 탐색
            q = [(i, j)]
            size = 0
            while q:
                x, y = q.pop()
                
                # 방문 체크
                if board[x][y] == 'X':
                    continue
                size += int(board[x][y])
                board[x][y] = 'X'
                
                # 4방향 탐색
                for a, b in move:
                    dx, dy = x+a, y+b
                    if dx < 0 or dx >= N or dy < 0 or dy >= M or board[dx][dy] == 'X':
                        continue
                    
                    q.append((dx, dy))
            else:
                res.append(size)
    
    return sorted(res) if res else [-1]