[프로그래머스] 무인도 여행 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 무인도를 각각 찾아내어 머무를 수 있는 날을 계산한 뒤, 모든 무인도의 머무를 수 있는 날을 오름차순으로 정렬하는 문제이다.

각 연결되어 있는 무인도를 찾기 위해 bfs 알고리즘을 활용한다.

각 무인도의 시작 위치를 찾아내어 연결된 무인도를 탐색하고 해당 무인도의 머무를 수 있는 날을 계산한다.

지도의 모든 위치를 탐색하며 무인도를 모두 찾아내고 각 무인도마다 머무를 수 있는 날을 저장했다면 이를 오름차순으로 정렬한다.

 

1. bfs 함수에서 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 지도의 각 문자열을 분리하여 2차원 리스트로 다시 저장한다. maps = list(list(i) for i in maps)
3. 시작 위치의 좌표를 입력받는 bfs 함수를 구현한다. def bfs(x, y)
4. 각 위치를 지나왔는지 확인할 리스트를 생성한다. arr = list(list(False for i in range(len(maps[0]))) for i in range(len(maps)))
5. 각 위치별 다음 위치로 이동할 수 있는 상, 하, 좌, 우 4가지 방향을 리스트로 저장한다. move = [[0, -1], [0, 1], [1, 0], [-1, 0]]
6. 시작 위치 0, 0부터 시작해 for i in range(len(maps)): for j in range(len(maps[i]))
7. 각 위치별로 연결된 하나의 무인도를 탐색합니다. result = bfs(i, j)
8. 만약 무인도에 머무를 수 있으면 if (result != 0)
9. 머무를 수 있는 날을 추가한다. answer.append(result)
10. 만약 무인도가 존재하지 않는다면 -1을 저장한다. if (len(answer) == 0): answer = [-1]
11. 반면 무인도가 존재한다면 머무를 수 있는 날을 오름차순으로 정렬한다. else: answer.sort()
    

bfs 함수

1. 만약 해당 위치가 바다라면 if (maps[x][y] == 'X')
2. 0을 반환한다. return 0
3. 해당 위치가 무인도라면 해당 위치를 저장할 deque를 생성한다. queue = deque()
4. 생성한 deque에 해당 위치의 좌표를 추가한다. queue.append([x, y])
5. 해당 무인도에 머무를 수 있는 날을 저장할 변수를 생성하고 초기화한다. result = 0
6. 만약 해당 위치가 처음 탐색하는 위치이면 if (not arr[x][y])
7. 해당 위치를 탐색함으로 수정하고 arr[x][y] = True
8. 해당 무인도에 머무를 수 있는 날을 더한다. result += int(maps[x][y])
9. 무인도를 탐색할 좌표가 있으면 반복한다. while (queue)
10. 현재 위치의 좌표를 가져온다. x, y = queue.popleft()
11. 해당 위치에서 다음 위치로 이동할 수 있는 4가지 방향에 따른 다음 위치를 탐색한다. for i in range(len(move))
12. 다음 위치의 좌표를 각각 저장한다. newX = x + move[i][0]  newY = y + move[i][1]
13. 만약 다음 위치가 이동 가능한 위치이고 if (0 <= newX < len(maps)) and (0 <= newY < len(maps[0]))
14. 만약 해당 위치를 처음 탐색하는 위치라면 if (not arr[newX][newY])
15. 해당 위치를 탐색함으로 수정하고 arr[newX][newY] = True
16. 만약 지도에서 해당 위치가 무인도라면 if (maps[newX][newY] != 'X')
17. 해당 위치를 이어서 탐색할 위치로 추가한다. queue.append([newX, newY])
18. 해당 무인도에 머무를 수 있는 날을 더한다. result += int(maps[newX][newY])
19. 연결된 한 무인도를 찾았다면 해당 무인도에 머무를 수 있는 날을 반환한다. return result

반응형

3. 소스코드

from collections import deque

def solution(maps):
    answer = []
    
    maps = list(list(i) for i in maps)

    def bfs(x, y):
        if (maps[x][y] == 'X'):
            return 0
        
        queue = deque()
        queue.append([x, y])
        
        result = 0
        if (not arr[x][y]):
            arr[x][y] = True
            result += int(maps[x][y])
        
        while (queue):
            x, y = queue.popleft()
            for i in range(len(move)):
                newX = x + move[i][0]
                newY = y + move[i][1]

                if (0 <= newX < len(maps)) and (0 <= newY < len(maps[0])):
                    if (not arr[newX][newY]):
                        arr[newX][newY] = True
                        if (maps[newX][newY] != 'X'):
                            queue.append([newX, newY])
                            result += int(maps[newX][newY])
                        
        return result
    
    arr = list(list(False for i in range(len(maps[0]))) for i in range(len(maps)))
    move = [[0, -1], [0, 1], [1, 0], [-1, 0]]
    for i in range(len(maps)):
        for j in range(len(maps[i])):
            result = bfs(i, j)
            if (result != 0):
                answer.append(result)
            
    if (len(answer) == 0):
        answer = [-1]
    else:
        answer.sort()

    return answer