[Programmers] Lv 2. 무인도 여행

문제:

풀이방법:

 숫자를 만난 순간부터 계속해서 숫자를 연속해서 탐지할 수 있도록 알고리즘을 구성해야 하고 따라서 DFS를 사용해서 해당 문제를 풀었다.

 maps를 탐색하다가 X가 아니고, 이전에 탐색한 곳이 아니라면 DFS를 수행하며, 연속된 영역을 탐색하는 동안 visited를 계속해서 갱신하도록 한다. 이와 같은 과정을 방문할 곳이 남아 있지 않을 때까지 수행하고, 각 영역의 넓이는 마지막에 정렬을 하도록 한다.(단, 정렬할 영역이 없다면 -1을 반환)

from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
def dfs(x, y, maps, visited):
    area = int(maps[x][y])
    queue = deque([(x,y)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<len(maps) and 0<=ny<len(maps[0]):
                if maps[nx][ny]!='X' and visited[nx][ny]==0:
                    area+=int(maps[nx][ny])
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
    return area, visited
 
def solution(maps):
    visited = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    answers = []
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j]!='X' and visited[i][j]==0:
                visited[i][j] = 1
                answer, visited = dfs(i, j, maps, visited)
                answers.append(answer)
 
    if len(answers):
        return sorted(answers)
    else:
        return [-1]

문제링크:

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

프로그래머스