[프로그래머스/그래프 탐색/LV2] 무인도 여행

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

프로그래머스

 

from collections import deque
def solution(maps):
    answer = []
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    new_map = []
    
    for i in range(len(maps)):
        new_map.append(list(maps[i]))
    
   
    for i in range(len(new_map)):
        for j in range(len(new_map[0])):
            if new_map[i][j] != 'X':
                
                cnt = 0
                dq = deque()
                dq.append((i,j))
                
                cnt += int(new_map[i][j])
                new_map[i][j] = 'X'
                
                while dq:
                    x,y = dq.pop()
                    for k in range(len(dx)):
                        nx = x+dx[k]
                        ny = y+dy[k]
                        
                        if 0<=nx<len(new_map) and 0<=ny<len(new_map[0]):
                            if new_map[nx][ny] != 'X':
                                cnt += int(new_map[nx][ny])
                                new_map[nx][ny] = 'X'
                                dq.append((nx,ny)) 
                                
                answer.append(cnt)
    answer = sorted(answer)
    if len(answer) > 0:
        return answer
    else: 
        return [-1]

---

풀이

1. 전형적인 DFS, BFS 풀이

2. 처음에 주어진 배열이 문자열이기에 new_map[nx][ny] = 'X'가 바로 바꿔지지 않았음. 이를 개선하기 위해 문자열일 list로 변경 후 다시 저장

3. 마지막에 탐색을 계속하기 위해선 dq.append()를 계속 해주어야함