[Swift] BOJ 11967 불켜기 풀이

[Swift] BOJ 11967 불켜기 풀이

 

 

1. 문제 분석

 

일단 이 문제는 문제를 잘 읽어야 한다는 것을 "맞았습니다!"를 받고 알게 되는 문제이다. 대충 시간복잡도랑 불 켤 수 있는 방을 찾으면 되겠다해서 BFS를 기계적으로 구현하면 바로 틀리게 된다.

BFS 투어를 하고 있던 나는 순간이동 같은 개념인줄 알고 1, 1에서 1, 3으로 가고... 뭐 이런식으로 생각하고 처음 코드를 짰다가 빨간 "틀렸습니다"를 맛보게 되었다. 그런데 그 후에도, 스위치를 켠 방은 무조건 건너갈 수 있을 것이다라고 생각하고 코드를 짜버려서 또 틀렸습니다를 마주했다.

 

일단은 BFS로 현재 갈 수 있는 곳을 탐색해야 해서 이동하는 것은 맞다. 그런데 중요한 것은 암소가 "불이 켜진 방"으로만 갈 수 있다는 사실이다. 1, 1 방에서 1, 3의 불을 켤 수는 있다. 왜냐하면 1, 1은 항상 불이 켜져있으니까. 그런데, 그 후 다른 방으로 가야할 때, 다른 방들은 불이 켜져 있지 않으면 아무데도 갈 수 없으며 불을 켤 수 없다. 이 부분을 조심해야 한다. 그런데 최종적으로 구해야 하는 것은 "불이 켜진 방의 수"이다. 이 부분을 정확히 하고 가야 한다.

 

 

2. 풀이 생각

 

그렇다면, 일단은 1, 1에서 시작하게 된다. 1, 1에서 어떤 방의 불을 켤 수 있는지를 정리하는 3차원 배열을 두고, x, y를 인덱스로 사용해서 접근을 하는 방식으로 "x, y 위치에서 불을 켤 수 있는 방의 리스트"를 관리하기로 한다. 3차원 배열 graph[x][y]에는 (x: Int, y: Int)라는 튜플이 들어가게 되고, 어느 방에 들어갔을 때, 이 배열을 순회하면서 튜플이 가리키는 좌표의 방에 불을 켜주면 되는 것이다.

 

이를 위해 불을 켰는지를 확인할 수 있는 lit와 bfs에서 방문의 여부를 알 수 있는 visited Bool 배열을 둔다. 보통은 visited를 하나만 두지만, 여기에서는 불이 켜졌는지 여부에 따라 방문할 수 있는지가 갈리기 때문에 필요한 배열이었다. 

 

한편, 불이 켜졌지만, 당장은 방문할 수 없는 경우를 대비해야할 필요가 있었다. 그래서 당장은 불이 켜졌지만, 아직 방문할 수 없는 곳들을 따로 저장해두는 배열도 두고, 모든 접근 가능한 방들을 방문하고 나서 다시 못갔던 방까지 갈 수 있는지를 확인해주고 이 방에 스위치가 있는지를 확인해주는 방식으로 풀이를 생각했다.

 

 

3. 코드

 

func boj_11967() {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let (n, m) = (input[0], input[1])
    let directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    var graph = [[[(x: Int, y: Int)]]](repeating: [[(x: Int, y: Int)]](repeating: [(x: Int, y: Int)](), count: n + 1), count: n + 1)
    var visited = [[Bool]](repeating: [Bool](repeating: false, count: n + 1), count: n + 1)
    var lit = [[Bool]](repeating: [Bool](repeating: false, count: n + 1), count: n + 1)
    var queue = [(x: Int, y: Int)]()
    var waiting = [(x: Int, y: Int)]()  // 불이 켜졌지만 갈 수 없는 방들
    var result = 1
    
    for _ in 0..<m {
        let read = readLine()!.split(separator: " ").map { Int($0)! }
        graph[read[1]][read[0]].append((read[2], read[3]))
    }

    // 시작점
    queue.append((1, 1))
    visited[1][1] = true
    lit[1][1] = true
    
    while !queue.isEmpty {
        let point = queue.removeFirst()

        // 불을 켜는 작업
        for room in graph[point.y][point.x] {
            if !lit[room.y][room.x] {
                lit[room.y][room.x] = true
                result += 1
                waiting.append((room.x, room.y))  // 불이 켜졌지만 아직 방문 불가
            }
        }

        // 인접한 방들로 이동
        for dir in directions {
            let newX = point.x + dir.0
            let newY = point.y + dir.1
            
            if newX > 0 && newY > 0 && newX <= n && newY <= n && lit[newY][newX] && !visited[newY][newX] {
                visited[newY][newX] = true
                queue.append((newX, newY))
            }
        }

        // 불이 켜졌지만 갈 수 없던 방 다시 체크
        var i = 0
        while i < waiting.count {
            let room = waiting[i]
            var canVisit = false
            for dir in directions {
                let adjX = room.x + dir.0
                let adjY = room.y + dir.1
                if adjX > 0 && adjY > 0 && adjX <= n && adjY <= n && visited[adjY][adjX] {
                    canVisit = true
                    break
                }
            }
            if canVisit {
                visited[room.y][room.x] = true
                queue.append(room)
                waiting.remove(at: i)
            } else {
                i += 1
            }
        }
    }

    print(result)
}

 

 

굉장히 복잡한데, 위에서 설명한 풀이를 최대한 구현해놓은 것이다. BFS를 기본적으로 사용하면서 여러 케이스들을 떠올리고 구현을 하면 되는 문제였다. 다만, 이런 구현은 처음이라 시간이 굉장히 오래걸렸다.

 

BFS를 심화하여 사용하는 문제를 몇 번 더 풀어보면 푸는 감이 조금은 올 것 같다.