[프로그래머스]Lv2. 무인도 여행(Python)

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

프로그래머스

 

문제 접근

 

무인도에서 상하좌우 이동을 하여 인접한 무인도를 모두 탐색(BFS)

인접한 모든 무인도 방문 후 무인도의 합을 period에 추가 

 

1. 상하 좌우의 이동을 체크할 델타 리스트 dx, dy 선언 

2. 방문 여부를 나타내는 visited 리스트 생성 

 

코드

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def solution(maps):
    # 맵의 세로 길이와 가로 길이
    row, col = len(maps), len(maps[0])
    # 방문 여부를 체크할 2차원 리스트를 생성
    visited = [[False]*col for _ in range(row)]
    
    answer = []  # 각 지역의 합을 저장할 리스트
    
    for i in range(row):
        for j in range(col):
            # 현재 위치가 X가 아니고 아직 방문하지 않았다면 탐색을 시작
            if maps[i][j] != "X" and not visited[i][j]:
                period = 0  # 현재 지역의 숫자들의 합을 저장할 변수
                q = [(i, j)]  # BFS를 위한 큐, 시작 위치를 추가
                
                while q:
                    y, x = q.pop(0)  # FIFO 방식으로 변경
                    if visited[y][x]:  # 이미 방문한 위치라면 pass
                        continue
                    visited[y][x] = True  # 현재 위치를 방문 처리
                    period += int(maps[y][x])  # 현재 위치의 값을 period에 add
                    
                    # 상하좌우 네 방향에 대해 탐색을 수행
                    for k in range(4):
                        ny, nx = y + dy[k], x + dx[k]  # 다음 탐색 위치를 계산
                        # 다음 위치가 맵 안에 있고, X가 아니며, 아직 방문하지 않았다면 큐에 추가
                        if 0 <= nx < col and 0 <= ny < row and maps[ny][nx] != "X" and not visited[ny][nx]:
                            q.append((ny, nx))
                    
                answer.append(period)  # 현재 지역의 탐색이 끝나면 합계를 answer 리스트에 추가
    
    # answer 리스트에 값이 있으면 오름차순으로 정렬하여 반환, 없으면 [-1]을 반환
    return sorted(answer) if answer else [-1]

 

문제 회고

 

최근 코테를 보면서 상하좌우 이동에 대한 문제가 꼭 1개는 나오는 걸 확인했다.

사실 늘 그 문제는 제치고 다른 쉬운 구현 문제부터 풀었는데 이제 델타 리스트 선언 후 현재 위치를 기준으로 상하좌우 네 방향을 탐색하는 코드를 작성했으니 무조건 시도해 보아야겠다.