[Swift][BFS] 백준 12869번 (뮤탈리스크)

요구능력 : BFS

 

코드설명 : 

 

문제풀이는 유튜브 큰돌의터전님께서 정말 잘 설명해놓으셨다.

이보다 잘설명하기는 어려울것 같아서 혹시나 어떤방식으로 풀리는지 모르겠는 사람은 유튜브를 들어가보시길..

 

SCV가 3대 있다고 가정하고, 뮤탈리스크는 1번 SCV를 먼저 칠 수도있고, 2번 SCV를 먼저 칠 수도있고, 3번 SCV를 먼저 칠 수도있다.

그렇다면 뮤탈리스크가 공격하는 경우의 수는 총 6가지가 나오게된다.

let damage = [[1, 3, 9],
              [1, 9, 3],
              [3, 1, 9],
              [3, 9, 1],
              [9, 1, 3],
              [9, 3, 1]]

 

나는 N이 1~3까지 밖에 없길래 그냥 큐를 튜플 3개로 선언하고 arr이 3보다 작은경우에는 나머지칸에 0을 넣어줬다.

   if arr.count == 1 {
        queue.append(((arr[0], 0, 0),0))
    }else if arr.count == 2 {
        queue.append(((arr[0], arr[1], 0),0))
    }else{
        queue.append(((arr[0], arr[1], arr[2]),0))
    }

 

그리고 문제에서 SCV가 파괴된경우는 체력이 0 또는 그 이하인데 방문처리를 하기위해서는 배열의 인덱스에 음수가 들어가서는 안되므로 음수가 된경우는 0으로 처리해줬다.

func bfs(){
    if arr.count == 1 {
        queue.append(((arr[0], 0, 0),0))
    }else if arr.count == 2 {
        queue.append(((arr[0], arr[1], 0),0))
    }else{
        queue.append(((arr[0], arr[1], arr[2]),0))
    }

    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0.0 == 0 && pop.0.1 == 0 && pop.0.2 == 0 {
            print(pop.1)
            break
        }

        for i in 0..<6{
            var a = pop.0.0 - damage[i][0]
            var b = pop.0.1 - damage[i][1]
            var c = pop.0.2 - damage[i][2]
            if a >= 0 && b >= 0 && c >= 0{
                if !visited[a][b][c]{
                    queue.append(((a, b, c), pop.1 + 1))
                    visited[a][b][c] = true
                }
            }else{
                if a < 0 {
                    a = 0
                }
                if b < 0 {
                    b = 0
                }
                if c < 0 {
                    c = 0
                }
                if !visited[a][b][c]{
                    queue.append(((a, b, c), pop.1 + 1))
                    visited[a][b][c] = true
                }
            }

        }
    }
}

 

 

후기 : 막상 알고나면 풀기 쉬운문제 핑계같지만 DP카테고리에 있어서 DP만 생각하다가 못풀겠더라는..

 

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let damage = [[1, 3, 9],
              [1, 9, 3],
              [3, 1, 9],
              [3, 9, 1],
              [9, 1, 3],
              [9, 3, 1]]
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 61), count: 61), count: 61)

var queue = [((Int, Int, Int), Int)]()

func bfs(){
    if arr.count == 1 {
        queue.append(((arr[0], 0, 0),0))
    }else if arr.count == 2 {
        queue.append(((arr[0], arr[1], 0),0))
    }else{
        queue.append(((arr[0], arr[1], arr[2]),0))
    }

    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0.0 == 0 && pop.0.1 == 0 && pop.0.2 == 0 {
            print(pop.1)
            break
        }

        for i in 0..<6{
            var a = pop.0.0 - damage[i][0]
            var b = pop.0.1 - damage[i][1]
            var c = pop.0.2 - damage[i][2]
            if a >= 0 && b >= 0 && c >= 0{
                if !visited[a][b][c]{
                    queue.append(((a, b, c), pop.1 + 1))
                    visited[a][b][c] = true
                }
            }else{
                if a < 0 {
                    a = 0
                }
                if b < 0 {
                    b = 0
                }
                if c < 0 {
                    c = 0
                }
                if !visited[a][b][c]{
                    queue.append(((a, b, c), pop.1 + 1))
                    visited[a][b][c] = true
                }
            }

        }
    }
}
bfs()