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

문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

접근 방법 

• 가능한 이웃 지점들을 모두 탐색하는 bfs 유형
• 아직 방문하지 않고, X가 아닌 곳 bfs 수행, 이웃한 섬을 차례로 방문, 방문 섬의 식량을 더해나간다. 더 이상 이웃한 섬이 없을때까지 계속함

 

문제 풀이 

1. maps의 격자 하나씩 탐색하면서 not visited & X가 아닌 곳 bfs 수행 
   - bfs: 시작 지점부터 상하좌우 이웃한 지점 살펴보면서 not visited & X가 아닌 곳 방문 
             -> 해당 지점의 식량을 cnt에 더하고, 큐에 넣고 방문처리 !!bfs함수 나와서도 방문처리가 유지되어야 하므로 visited 배열은 전역변수로 선언한다!!
   - 더이상 이웃한 섬이 없을 때까지 반복 
   - 이웃한 섬들의 식량 합(cnt) 리턴 
2. answer에 식량합 추가 
3. bfs 종료 후 그 다음 방문하지 않고, X가 아닌 곳 다시 bfs 수행  
4. 모든 지점 탐색후 answer 오름차순 정렬 후 리턴 

 

구현 코드 

from collections import deque 
visited = []
def bfs(x, y, n, m, board):
    global visited 
    
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    visited[x][y] = True 
    q = deque()
    q.append((x, y))
    cnt = int(board[x][y])
    while q:
        i, j = q.popleft()
        for d in range(4):
            ni = i + dx[d]
            nj = j + dy[d]
            if ni<0 or ni>=n or nj <0 or nj>=m or visited[ni][nj]: # 범위를 벗어나거나 이미 방문했으면 continue 
                continue
            if board[ni][nj] != "X": #X가 아니라면 큐에 추가하고 방문, 해당 칸의 식량 +
                q.append((ni, nj))
                visited[ni][nj] = True 
                cnt += int(board[ni][nj])
        
    return cnt
                
    

def solution(maps):
    global visited 
    answer = []
    
    n, m = len(maps), len(maps[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    for i in range(n): #maps의 모든 지점 탐색하면서 not visited & X가 아닌 지점 찾기
        for j in range(m):
            if visited[i][j]:
                continue 
            if maps[i][j] != "X":
                answer.append(bfs(i, j, n, m, maps)) #해당 지점과 이웃한 섬들의 모든 식량 합 리턴 
    
    if not answer:
        return [-1]
    
    answer.sort()
    return answer