Python) 프로그래머스 - 무인도 여행

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

프로그래머스

실행코드

import collections


DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]

def solution(maps):
    num_rows, num_cols = len(maps), len(maps[0])
    
    visited = [[False for _ in range(num_cols)] for _ in range(num_rows)]
    
    periods = []
    
    for i in range(num_rows):
        for j in range(num_cols):
            if maps[i][j] != "X" and not visited[i][j]:
                period = 0
                q = collections.deque([(j, i)])
                
                while q:
                    x, y = q.popleft()
                    if visited[y][x]:
                        continue
                    visited[y][x] = True
                    period += int(maps[y][x])
                    
                    for direction in range(4):
                        new_x, new_y = x + DX[direction], y + DY[direction]
                        if (0 <= new_x < num_cols and 0 <= new_y < num_rows and
                            maps[new_y][new_x] != "X" and not visited[new_y][new_x]):
                            q.append((new_x, new_y))
                
                periods.append(period)
    
    if not periods:
        return [-1]
    
    return sorted(periods)

풀이

solution 함수의 솔루션 방법은 입력 배열에 있는 숫자의 연결된 구성 요소에 대한 BFS 순회입니다.

 

이 메서드는 연결된 구성 요소에서 방문할 셀을 포함하는 deque q와 연결된 구성 요소의 기간을 추적하는 카운터 변수 period를 사용합니다.

while 루프의 각 반복에서 메서드는 deque의 popleft() 메서드를 사용하여 q에서 가장 왼쪽 셀을 제거합니다.

그런 다음 visited 2D 배열을 사용하기 전에 셀을 방문한 적이 있는지 확인합니다.

방문한 경우 루프는 다음 반복으로 계속됩니다.

그렇지 않으면 메서드는 해당 요소를 True로 설정하여 visited 2D 배열에서 셀을 방문한 것으로 표시합니다. 또한 셀의 숫자 값을 주기 카운터에 추가합니다.

그런 다음 메서드는 DX를 사용하여 네 방향 모두에서 현재 셀의 방문하지 않은 이웃을 확인합니다. 

각 이웃에 대해 메서드는 유효한 셀(즉, 입력 배열의 경계 내부)인지, 장애물(즉, "X")이 아닌지, 이전에 방문한 적이 없는지 확인합니다.

이러한 조건이 모두 참이면 메서드는 append() 메서드를 사용하여 deque q에 이웃의 좌표를 추가합니다.

BFS 순회가 계속됩니다. deque q가 비어 있을 때까지, 이는 연결된 구성 요소의 모든 셀을 방문했음을 의미합니다. 이때 메서드는 연결된 구성 요소의 모든 숫자의 합을 나타내는 주기 카운터를 반환합니다.

전체적으로 솔루션 함수의 솔루션 방법은 입력 배열에서 숫자들의 연결된 구성요소에 대한 BFS 트래버설을 수행하고, 숫자 값들을 주기 카운터에 추가하고, 주기 카운터를 연결된 구성요소의 주기로 반환합니다.