[PRO] 무인도 여행 | Python

문제

프로그래머스 코딩테스트 연습  > 연습문제 > 무인도 여행 | Lv.2

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

프로그래머스

 

 

 

 

 

풀이 과정

파이썬 풀이

from collections import deque

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

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    answer = []
    visited = [[False] * m for _ in range(n)]
    
    def bfs(x, y, n, m):
        cnt = int(maps[x][y])
        q = deque()
        q.append((x, y))
        visited[x][y] = True
        
        while q:
            x, y = q.popleft()
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if maps[nx][ny] == "X" or visited[nx][ny]:
                    continue
                visited[nx][ny] = True
                q.append((nx, ny))
                cnt += int(maps[nx][ny])
        return cnt

        
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "X" or visited[i][j]:
                continue
            cnt = bfs(i, j, n, m)
            answer.append(cnt)
    if not answer:
        answer = [-1]
    else:
        answer.sort()
    
    return answer

• maps를 순회하며 X가 아니고 방문한 적 없으면 bfs를 실행해서 칸의 숫자를 모두 더하고(cnt), 함수가 종료되면 answer에 추가
• 이때 최단거리를 구하는 게 아니라 갈 수 있는 곳의 숫자를 더하는 것이므로 bfs가 아닌 dfs를 사용해도 된다.
• 백준의 2667번 단지번호붙이기 문제와 유사하다.
  https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기