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

오늘의 문제 - DFS/BFS

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

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

---

풀이 및 접근 방식

BFS 풀이

from collections import deque
def solution(maps):
    answer = []
    
    v = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    
    def bfs(sx, sy):
        cnt = int(maps[sx][sy])
        v[sx][sy] = True
        queue = deque([[sx, sy]])
        
        dx = [0, 0, -1, 1]
        dy = [1, -1, 0, 0]
        while queue:
            cx, cy = queue.popleft()
            
            for i in range(4):
                nx = cx + dx[i]
                ny = cy + dy[i]
                
                if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                    if maps[nx][ny] != 'X'and not v[nx][ny]: # 숫자이면서 방문하지 않은 경우
                        
                        v[nx][ny] = True
                        cnt += int(maps[nx][ny])
                        queue.append([nx, ny])
                        
        return cnt
    
    for r in range(len(maps)):
        for c in range(len(maps[0])):
            if maps[r][c] != 'X' and not v[r][c]:
                answer.append(bfs(r, c))
                
    answer.sort()
    if not answer:
        return [-1]
    
    return answer

풀이

 

1. 방문 여부를 기록할 리스트 v 초기화
2. BFS 함수 정의 (bfs(sx, sy)):
   • bfs 함수는 현재 위치 (sx, sy)에서 출발하여 연결된 모든 숫자를 탐색하고, 그 합을 계산한다.
   • 큐를 사용하여 현재 위치에서 인접한 4방향(상, 하, 좌, 우)으로 이동하면서 탐색한다.
   • 이동한 위치가 유효하고 아직 방문하지 않았으며 숫자라면 방문 표시를 하고, 그 값을 cnt에 더한다.
   • 탐색이 끝나면 해당 영역의 숫자의 합을 반환한다.
3. 모든 위치에 대해 BFS 수행
   • 맵 전체를 순회하면서 숫자가 있고 아직 방문하지 않은 위치에서 BFS를 시작한다.
   • 각 BFS 호출의 결과를 answer 리스트에 추가한다.
4. 결과 처리
   • answer 리스트를 오름차순으로 정렬한다.
   • 만약 answer가 비어 있다면, [-1]을 반환한다.
   • 그렇지 않다면 answer 리스트를 반환한다.

 

DFS 풀이

def solution(maps):
    answer = []
    
    v = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    
    def dfs(x, y):
        v[x][y] = True
        cnt = int(maps[x][y])
        
        dx = [0, 0, -1, 1]
        dy = [1, -1, 0, 0]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                if maps[nx][ny] != 'X' and not v[nx][ny]: # 숫자이면서 방문하지 않은 경우
                    cnt += dfs(nx, ny)
                    
        return cnt
    
    for r in range(len(maps)):
        for c in range(len(maps[0])):
            if maps[r][c] != 'X' and not v[r][c]:
                answer.append(dfs(r, c))
                
    answer.sort()
    if not answer:
        return [-1]
    
    return answer

---

회고

지도 관련 문제는 DFS랑 BFS를 관련 문제로 자주 나오니 잘 익혀둘 필요가 있다.

근데 항상 DFS BFS 함수에서 결과값을 반환할지, 전역변수를 사용할지 문제 풀 때마다 고민하는 것 같긴 하다. 하나를 정해서 확실히 푸는 속도를 줄이는 것이 좋을 것 같다.

32일차~~고고고