[99클럽 코테 스터디 4일차 TIL] 백준 안전 영역 Swift

오늘의 문제

- 백준 안전 영역

- https://www.acmicpc.net/problem/2468

 

오늘의 학습 키워드

- BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

- BFS + Queue

- DFS + Stack

 

BFS (너비 우선 탐색)

- 최단 거리, 최소 횟수, 최소 비용 같은 최소 문제를 해결 할 때 자주 사용된다.

- 모든 경우를 한 단계씩 탐색하기 때문에 최단 거리 문제에서 유리하다.

- Queue 를 사용해서 같은 레벨 순으로 탐색하기 때문에 최단 거리를 자연스럽게 구할 수 있다.

- 그래프에서 연결된 영역을 탐색하는 문제에서도 유용하다.

- 섬의 개수 찾기, 감염된 영역 구하기, 색칠된 영역 구하기 등 ..

 

DFS (깊이 우선 탐색)

- 그래프나 트리에서 한 방향으로 끝까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식이다.

- 한 방향으로 깊이 들어가기 때문에 "최소 거리"를 보장하기 어렵다.

- 스택이나, 재귀를 사용해서 구현 가능하다.

- 경로 개수 찾기, 완전 탐색, 백트래킹(최적의 조합 찾기) 같은 문제에 많이 쓰인다.

 

접근 방법

BFS vs DFS

- 해당 문제는 그래프에서 연결된 영역 (= 빗물이 넘치지 않는 안전 영역)을 찾기 때문에 BFS 로 접근한다.

- BFS 를 사용하면 한 영역을 모두 탐색한 후에 새로운 영역을 찾아서 탐색할 수 있다.

- DFS 도 가능하지만, BFS 는 큐를 사용해서 구현하기 쉽고 직관적이다.

 

Queue

- Swift 에서는 Queue 를 기본으로 제공하지 않기 때문에 일반 List 를 통해 구현했다.

- First In First Out 으로 동작해야하기 때문에 인자를 꺼낼때는 removeFirst() 메소드를 사용한다.

- Queue 는 O(1) 이지만 List 에서는 (n) 의 작업이다.

- 인자를 추가할 때에는 append() 메소드를 사용하고, O(1) 의 작업이다.

 

문제 풀이

func calculateSafeArea(n: Int, h: Int, originalMap: [[Int]]) -> Int {
    var visitMap = originalMap
    var queue = [(Int, Int)]() // 가까운 노드를 먼저 방문해야해서 순서를 보장해야함
    var count = 0
    let dy = [-1, 1, 0, 0]
    let dx = [0, 0, -1, 1]

    for y in 0..<n {
        for x in 0..<n {
            // 현재 물에 잠기지 않는 지점
            guard visitMap[y][x] > h else { continue }
            count += 1 // 물에 잠기지 않는 영역
            visitMap[y][x] = 0 // 다른 지점에서 방문할 때 이미 방문했음을 체크
            queue.append((y, x)) // 현재 지점부터 상하좌우를 체크하기 위해 큐에 추가

            while queue.isEmpty == false {
                let (cy, cx) = queue.removeFirst() // O(n)

                for m in 0..<4 {
                    let ny = cy + dy[m]
                    let nx = cx + dx[m]
                    guard ny >= 0, ny < n, nx >= 0, nx < n,  // index 체크
                          visitMap[ny][nx] > h else { continue } // 주변이 물에 잠기지 않는 지점인지 체크
                    visitMap[ny][nx] = 0
                    queue.append((ny, nx))
                }
            }
        }
    }

    return count
}

func readInput() -> (Int, Int, [[Int]])? {
    guard let input = readLine(), let n = Int(input) else { return nil }
    var inputArray = [[Int]]()
    var maxItem = Int.min

    for _ in 0..<n {
        guard let input = readLine() else { continue }
        inputArray.append(input.compactMap {
            guard let item = Int(String($0)) else { return nil }
            maxItem = max(maxItem, item)
            return item
        })
    }


    return (n, maxItem, inputArray)
}

if let (n, maxHeight, originalMap) = readInput() {
    var result = Int.min

    for h in 0..<maxHeight {
        let count = calculateSafeArea(n: n, h: h, originalMap: originalMap)
        result = max(result, count)
    }

    print(result)
}

 

- 반례 기준으로 전부 체크했는데 결과가 틀림으로 나온다

 

 

오늘의 회고

- DFS, BFS 기본적인 문제를 더 풀어보기

- Deque (Double-ended Queue) 를 구현해보기

- Swift 에서는 ArraySlice 또는 LinkedList 를 사용해서 구현할 수 있다.