BFS

문제집 링크

문제 분류	문제	문제 제목	확인
연습 문제	1926	그림	✅ 시작점 여러 개
연습 문제	2178	미로 탐색	✅ 시작점으로부터 거리 계산
연습 문제	7576	토마토
연습 문제	4179	불!
연습 문제	1697	숨바꼭질
기본 문제✔	1012	유기농 배추	✅ 시작점 여러 개
기본 문제✔	10026	적록색약
기본 문제✔	7569	토마토
기본 문제✔	7562	나이트의 이동
기본 문제✔	5427	불
기본 문제	2583	영역 구하기
기본 문제	2667	단지번호붙이기
기본 문제	5014	스타트링크
기본 문제	2468	안전 영역
기본 문제	6593	상범 빌딩

BFS

// 출처 ㅣ https://velog.io/@aurora_97/%EB%B0%B1%EC%A4%80-1926%EB%B2%88-%EA%B7%B8%EB%A6%BC-Swift
func bfs(_ sx: Int, _ sy: Int) -> Int {
    var width = 1
    arr[sx][sy] = 0
    
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    
    var idx = 0
    var queue = [(sx,sy)]
    
    while queue.count > idx {
        let (cx,cy) = queue[idx]
        idx += 1
        
        for i in 0..<4 {
            let nx = cx + dx[i]
            let ny = cy + dy[i]
            
            if (0..<n) ~= nx && (0..<m) ~= ny && arr[nx][ny] == 1{
                arr[nx][ny] = 0
                queue.append((nx,ny))
                width += 1
            }
        }
    }

    return width
}

• Swift에서는 Deque 자료구조를 지원하지 않는다. 그렇기 때문에 Queue에서 첫번째 원소를 pop 할 때 시간복잡도가 O(N)이기 때문에 시간 초과가 발생할 가능성이 높다. 따라서 이 부분을 잘 신경써주어야 하는데 index 기법을 많이 사용하는 것 같더라.
• while문의 조건이 이해가 처음에 안 될 수 있는데 Queue에 더 이상 pop 할 원소가 남아있지 않음을 의미한다고 생각하면 된다. 더 이상 원소를 추가해주는 작업 없이 pop만 하다보면 idx가 큐의 count를 초과하는 경우가 생기는데 이 때 bfs를 종료한다.