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

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

프로그래머스

 

탐색 문제이다. 한 무인도마다 모든 머무를 수 있는 곳을 모두 방문하면 끝인 문제이다.

 

1. maps라는 2중 배열로 입력값을 정리한다.

2. 모든 좌표에서 머를 수 있는 곳이라면, 즉 "X"가 아니라면 탐색 시작

2-1. stack을 만들고 지금의 좌표를 넣는다.

2-2. can_stay를 0으로 초기화하고, 지금 위치의 머무를 수 있는 일수를 더해준다.

2-3. 그리고, 지금의 위치를 "X"로 만들어 방문했다는 표시를 한다.

3. DFS를 가장한 BFS 시작? --> 사실 어떻게 하던 상관이 없다.

3-1. stack에서 pop 해주고 4방향에 대한 탐색 시작

3-2. 가는 위치가 유효한 위치이고 "X"가 아니라면 can_stay에 더해주고 지금 위치를 "X"로 만들고 stack에 추가

 

 

def solution(maps):
    answer = []
    
    d = [[0,1],[0,-1],[-1,0],[1,0]]
    
    max_y, max_x = len(maps), len(maps[0])
    
    for index in range(max_y):
        maps[index] = list(i for i in maps[index])
    
    for y in range(max_y):
        for x in range(max_x):
            if maps[y][x] != "X":
                stack = [(y,x)]
                can_stay = 0
                can_stay += int(maps[y][x])
                maps[y][x] = "X"
                
                while stack:
                    now_y, now_x = stack.pop()
                    
                    for dy, dx in d:
                        new_y = now_y + dy
                        new_x = now_x + dx
                        if 0 <= new_y < max_y and 0 <= new_x < max_x and maps[new_y][new_x] != "X":
                            can_stay += int(maps[new_y][new_x])
                            maps[new_y][new_x] = "X"
                            stack.append((new_y,new_x))
                            
                answer.append(can_stay)
    
    if not answer:
        answer = [-1]
    else:
        answer.sort()
    
    return answer

탐색 문제!