무인도 여행

날짜 : 2023. 10. 06

사용 언어 : python

 

문제

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

 

 

코드

from collections import deque
def solution(graph):
    n, m = len(graph), len(graph[0])  # 행, 열
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    def bfs(r, c):
        queue = deque()
        queue.append([r, c])
        cnt = int(graph[r][c])
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx in range(n) and ny in range(m):  # 범위 확인
                    if not visited[nx][ny] and graph[nx][ny] != 'X':  # 방문 x, 무인도인 경우
                        cnt += int(graph[nx][ny])  # 식량 개수 증가
                        visited[nx][ny] = True  # 방문처리
                        queue.append([nx, ny])
        return cnt
    
    res = list()
    visited = [[False] * m for _ in range(n)]  # 방문체크용
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and graph[i][j] != 'X':  # 방문 x, 무인도
                # print(i, j)
                visited[i][j] = True  # 방문처리
                res.append(bfs(i, j))
                
    if len(res) == 0: return [-1]
    else: 
        res.sort()
        return res

 

 

풀이

- 일반적인 BFS 방식으로 풀이하는 문제였다.

- 지도에서의 행과 열의 길이를 구한 다음, 무인도를 찾을 때마다 BFS를 실행해 해당 값을 리스트 res에 넣는다.

- 만약 res의 길이가 0인 경우는 전부 바다인 케이스이기 때문에 -1을 리턴하고, 그 이외에는 정렬한 리스트 res를 리턴한다.

 

 

알게된 점

- 기본적인 BFS문제였지만 백준과는 다르게 여기서는 딱히 지도의 길이를 제공해주지 않아 처음에는 원하는 답이 나오지 않았었다.

- 그러다 직접 적은 그래프 길이를 확인해보니 서로 다른 것을 확인, 곧바로 풀이할 수 있었다.

 

 

참고 사이트

-