[Python] 파이썬 프로그래머스 무인도 여행

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

프로그래머스

---

나의 풀이

DFS를 이용하여 섬을 만나면 주변 섬 전체를 탐색하도록 설계하였다.

need_visit에는 탐색해야하는 값의 (행, 열)이 들어있고 pop을 통해 빼낸다. visit을 따로 설정해두어 이미 둘러본 섬은 다시 둘러보지 않도록 설계한다.

 

pop으로 꺼낸 섬의 주변을 탐색하고 섬이 있다면 need_visit에 추가하여 붙어있는 섬을 다 탐색하도록 한다.

 

def solution(maps):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    answer = []
    period = 0
    row, col = len(maps), len(maps[0])
    print(row, col)
    visited = [[True]*col for _ in range(row)]

    for i in range(row):
        for j in range(col):
            if maps[i][j] != 'X' and visited[i][j]:
                need_visit = [(i, j)]
                period = 0

                while need_visit:
                    x, y = need_visit.pop(0)
                    if visited[x][y]:
                        period += int(maps[x][y])
                        visited[x][y] = False
                        for k in range(len(dx)):
                            mx, my = x+dx[k], y+dy[k]
                            if (-1 < mx < row) and (-1 < my < col):
                                if  maps[mx][my] != 'X' and visited[mx][my]:
                                    need_visit.append((mx, my))
                answer.append(period)
    answer.sort()
    if answer == list():
        return [-1]
    return answer