[Python 문제 풀이] 프로그래머스 '무인도 여행'

Programmers Lv.2 '무인도 여행' 파이썬

영역 탐색 -> BFS

조건파악

1. 영역 탐색

2. 탐색하면서 수를 누산해야 함

 

접근

recursive BFS를 이용.

 

의사코드

bfs()를 선언

bfs()는 재귀적으로 호출되며, 특정 지점에서 네 방향을 탐색하고 방문처리

유효한 탐색 방향에 대해 다시 bfs() 수행 후 결과들을 합산

bfs를 시작한 지점에서의 결과와 다시 합산하여 return

방문하지 않은 지점을 우선으로 전부 탐색하여 결과를 리스트에 저장

리스트를 정렬. 리스트가 비어있으면 [-1]

 

구현

import sys
sys.setrecursionlimit(10**6)

def solution(maps):
    answer = []
    rows = len(maps)
    cols = len(maps[0])
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    vis = [[False for _ in range(cols)] for _ in range(rows)]

    #recursive bfs
    def bfs(r,c) :
        vis[r][c] = True
        area = 0
        for i in range(4) :
            r1,c1 = r + dr[i], c + dc[i]
            if 0 <= r1 < rows and 0 <= c1 < cols and maps[r1][c1] != 'X' and not vis[r1][c1] :
                area += bfs(r1,c1) 
        return int(maps[r][c]) + area

    #start search
    for i in range(rows) :
        for j in range(cols) :
            if vis[i][j] == False and maps[i][j] != 'X':
                answer.append(bfs(i,j))

    #validate answer
    if answer :
        answer.sort()
    else :
        answer = [-1]
    return sorted(answer)