[Swift][BFS] 백준 14395번 (4연산)

요구능력 : BFS

 

코드설명 : 

 

이 문제의 핵심

1) 출력을 연산횟수가아닌 사용한 연산자를 출력해야한다.

2) 가능한 방법이 여러가지라면, 사전 순으로 앞서는 것을 출력한다.

 

최소 연산횟수를 구하라고 했으니 BFS를 의심해보고 1~4번까지 연산을 주어준걸보니 BFS가 확실하다고 생각했다.

 

1) 출력을 연산횟수가아닌 사용한 연산자를 출력해야한다.

연산자를 출력해야 하므로 queue에 계속해서 연산자를 쌓아주기 위해서 quque를 (s, String배열)튜플로 관리하였다.

var queue = [(Int, [String])]()
queue.append((s, []))

 

2) 가능한 방법이 여러가지라면, 사전 순으로 앞서는 것을 출력한다.

사전 순으로 앞선다고해서 따로 다른처리를 할 건 없고 큐의 특성을 이용하면된다.

큐는 FIFO(First-In-First-Out)이기 때문에, 먼저 들어간거 먼저나온다.

그래서 문제에서 주어진 아스키코드 순서대로 큐에 넣어주면 된다.

 

    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0 == t{
            isChange = true
            if pop.1.count == 0{
                print(0)
            }else{
                print(pop.1.map{String($0)}.joined(separator: ""))
            }
            break
        }
        var arr = pop.1
        if pop.0 * pop.0 <= 1000000000 {
            if !visited[pop.0 * pop.0]{
                arr.append("*")
                queue.append((pop.0 * pop.0, arr))
                visited[pop.0 * pop.0] = true
                arr.removeLast()
            }
        }
        
        if pop.0 + pop.0 <= 1000000000{
            if !visited[pop.0 + pop.0]{
                arr.append("+")
                queue.append((pop.0 + pop.0, arr))
                visited[pop.0 + pop.0] = true
                arr.removeLast()
            }
        }
        
        if pop.0 - pop.0 >= 0{
            if !visited[pop.0 - pop.0]{
                arr.append("-")
                queue.append((pop.0 - pop.0, arr))
                visited[pop.0 - pop.0] = true
                arr.removeLast()
            }
        }
        
        if pop.0 != 0 && !visited[pop.0 / pop.0]{
            arr.append("/")
            queue.append((pop.0 / pop.0, arr))
            visited[pop.0 / pop.0] = true
            arr.removeLast()
        }
    }
    if !isChange{
        print(-1)
    }
}

 

 

 

후기 : 문제가 어느정도 쉬운수준인거같은데 정답률이 엄청 낮은것 같다.

let st = readLine()!.split(separator: " ").map{Int(String($0))!}
let s = st[0]
let t = st[1]
var isChange = false
func bfs(){
    
    var visited = Array(repeating: false, count: 1000000001)
    var queue = [(Int, [String])]()
    
    queue.append((s, []))
    
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0 == t{
            isChange = true
            if pop.1.count == 0{
                print(0)
            }else{
                print(pop.1.map{String($0)}.joined(separator: ""))
            }
            break
        }
        var arr = pop.1
        if pop.0 * pop.0 <= 1000000000 {
            if !visited[pop.0 * pop.0]{
                arr.append("*")
                queue.append((pop.0 * pop.0, arr))
                visited[pop.0 * pop.0] = true
                arr.removeLast()
            }
        }
        
        if pop.0 + pop.0 <= 1000000000{
            if !visited[pop.0 + pop.0]{
                arr.append("+")
                queue.append((pop.0 + pop.0, arr))
                visited[pop.0 + pop.0] = true
                arr.removeLast()
            }
        }
        
        if pop.0 - pop.0 >= 0{
            if !visited[pop.0 - pop.0]{
                arr.append("-")
                queue.append((pop.0 - pop.0, arr))
                visited[pop.0 - pop.0] = true
                arr.removeLast()
            }
        }
        
        if pop.0 != 0 && !visited[pop.0 / pop.0]{
            arr.append("/")
            queue.append((pop.0 / pop.0, arr))
            visited[pop.0 / pop.0] = true
            arr.removeLast()
        }
    }
    if !isChange{
        print(-1)
    }
}

bfs()