[백준] 2665번 미로만들기 [Swift]

문제 링크

2665번: 미로만들기

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작 방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작 방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작 방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작 방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

문제 풀이

뭔가 미로 문제를 보면 BFS, DFS가 떠오르는 것 같아요.

근데 이 문제에서는 최단거리를 구하는 것이 아닌 검은 방을 최소한으로 바꿔서 목적지에 도착하는 것이 목적입니다.

저는 이 문제에서 BFS를 사용하는 풀이를 사용했습니다.

 

우선 방문했는지에 대한 여부는 이 문제에서 크게 상관은 없습니다.

하지만 방문했을 당시 방을 몇 번 바꿨는지는 중요한 정보입니다.

따라서 하나의 배열을 만들어서 해당 위치에 도착했을 때 방을 몇 번 바꿨는지를 저장하면 됩니다.

그리고 다음에 또 방문을 했을 때 그 전에 방문했을 때 방을 바꾼 횟수와 현재 방을 바꾼 횟수를 비교해서 작은 것으로 값을 바꿔주시면 됩니다!

 

새로운 배열을 하나 만들어 그 배열에 방을 바꾼 횟수를 저장하는 아이디어가 중요한 문제였던 것 같습니다.

소스 코드

import Foundation

class Queue<T>{
    var enqueue: [T]
    var dequeue: [T] = []
    
    var isEmpty: Bool{
        return enqueue.isEmpty && dequeue.isEmpty
    }
    var count: Int{
        return enqueue.count + dequeue.count
    }
    
    init(_ queue:[T]){
        self.enqueue = queue
    }
    
    func push(_ n: T){
        enqueue.append(n)
    }
    
    func pop() -> T?{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    
}

func solution() {
    let n = Int(String(readLine()!))!
    var maze: [[Int]] = []
    
    for _ in 0..<n {
        maze.append(readLine()!.map({Int(String($0))!}))
    }
    
    let dx: [Int] = [0,0, -1,1]
    let dy: [Int] = [-1,1, 0,0]

    let queue: Queue = Queue([[Int]]())
    // x좌료, y좌표
    queue.push([0,0])
    
    // 벽 부순 횟수
    var visited: [[Int]] = [[Int]](repeating: [Int](repeating: 99999, count: n), count: n)
    visited[0][0] = 0
    
    while(!queue.isEmpty) {
        guard let now = queue.pop() else { fatalError() }
        for i in 0..<dx.count {
            let nextX = now[0] + dx[i]
            let nextY = now[1] + dy[i]
            
            if nextX < 0 || nextX > n-1 || nextY < 0 || nextY > n-1 {
                continue
            } else {
                // 흰방일 때
                if maze[nextY][nextX] == 1 {
                    if visited[nextY][nextX] > visited[now[1]][now[0]] {
                        visited[nextY][nextX] = visited[now[1]][now[0]]
                        queue.push([nextX, nextY])
                    }
                // 검은방일 때
                } else {
                    if visited[nextY][nextX] > visited[now[1]][now[0]] + 1 {
                        visited[nextY][nextX] = visited[now[1]][now[0]] + 1
                        queue.push([nextX, nextY])
                    }
                }
            }
        }
    }
    print(visited[n-1][n-1])
}

solution()