99클럽 코테 스터디 32일차 TIL + BFS

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "무인도 여행" 문제를 풀었다.
- 오늘 주제는 DFS/BFS이다. 
- DFS/BFS 두 가지 방식 모두로 풀 수 있는 문제이지만 더 편한 BFS로 풀었다.

[나의 코드]

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    answer = []
    
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    visited = [[False] * m for _ in range(n)]
    
    def bfs(x, y):
        count = 0
        
        q = deque()
        q.append((x, y))
        visited[x][y] = True
        count += int(maps[x][y])
        
        while q:
            x, y = q.popleft()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0 <= nx < n and 0 <= ny < m:
                    if not visited[nx][ny] and maps[nx][ny] != 'X':
                        count += int(maps[nx][ny])
                        visited[nx][ny] = True
                        q.append((nx, ny))
        return count
    
    for i in range(len(maps)):
        for j in range(len(maps[i])):
            if maps[i][j] != 'X' and not visited[i][j]:
                answer.append(bfs(i, j))
    
    if answer:
        return sorted(answer)
    else:
        return [-1]

배열의 크기를 먼저 구해준다. 나중에 쓸 일이 많으므로 변수에 담아주었다.
상, 하, 좌, 우 이야기가 나왔으므로 이동할 수 있는 좌표를 만들어 주고, 방문 여부를 확인하는 배열도 만들어 주었다.

BFS 함수를 보면 정말 별 거 없다. 기본 코드에서 조건에 맞게 변형한 정도이다.
주의할 점은 count 변수에 int 형으로 형변환이 필요하다. 자세히 보니 문자열이더라. 이거 안 해줘서 시간 빼먹었다.

그리고 모든 배열 돌면서 X가 아닌 숫자라면 BFS 함수를 돌려줘서 answer 배열에 담는다.
만약 answer 배열에 원소가 존재하면 정렬해서, 없다면 -1만 넣어서 반환하면 끝이다.

[오늘의 회고]
- 그렇게 어려운 문제는 아니었다. 그냥 딱 기본 문제인 듯하다.
- 코테가 늘 이 정도 수준이라면 얼마나 행복할까? ^^;; 끝!