[Swift][BFS] 백준 14226번 (이모티콘)

요구능력 : BFS에 대한 이해와 응용

 

코드설명 : 

 

이 문제에서 가장 중요한건 조건을 보고 핵심을 캐치하는것이다.

내가 생각했을 때 핵심은 화면, 클립보드, 시간을 구성해서 큐와 visited배열을 짜는것이다.(조건은 문제를 잘 읽어보면 생각나기때문)

 

화면, 클립보드, 시간이 함께 움직이기(?) 때문에 하나의 튜플로 정의했다.

pop.0은 화면 pop.1은 클립보드 pop.2는 시간을 의미한다.

 

일반적으로 BFS에서 같은곳을 두번이상 방문하면 최단시간, 최단경로가 나오지 않으므로 방문처리를 해주는데,

방문여부를 표시하는 visited는 visited[1][0]이면 화면에 1개있고 클립보드가 0개있을 때 라는 의미이다.

이렇게 해준이유는 화면개수와 클립보드개수에 따라 다음번에 while문을 돌때 시간에 영향을 주는데 똑같은 곳을 두번 방문하게 되면 처음에는 짧은시간에 돌지만, 다음번에 방문할 때는 더 오래걸린 시간에 방문하기 때문에 중복방문을 방지해야한다.

 

1. 화면 이모티콘 모두 복사해서 클립보드에 저장

(이전에 클립보드에 있던 내용은 덮어쓰기가 된다.)

 

3. 화면에 있는 이모티콘 중 하나 삭제

 

1번과 3번을 묶어준 이유는 공통조건이 존재하기 때문이고 따로줘도 상관은없다.

이렇게 조건을 찾고 다른 BFS와 마찬가지로 방문여부 확인 후 방문처리를 해주고 queue에 넣어주었다.

 

1번의 경우에 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장하는데, 이전에 클립보드에 있던 내용은 덮어쓰기가 되니까 결국 화면에 있는 이모티콘만 클립보드에 저장된다는 말이다. 따라서 클립보드 자리에 pop.0이 들어간것이다.

 

3번의 경우에 화면에 있는 이모티콘 중 하나를 삭제하는 거니까 간단하게 화면자리에 pop.0(화면) - 1을 해준것이다.

if pop.0 >= 1 && pop.0 < 2000{
            if !visited[pop.0][pop.0]{ //1번
                visited[pop.0][pop.0] = true
                queue.append((pop.0,pop.0,pop.2 + 1))
            }

            if !visited[pop.0 - 1][pop.1]{ //3번
                visited[pop.0 - 1][pop.1] = true
                queue.append((pop.0 - 1, pop.1, pop.2 + 1))
            }
        }

 

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기

(클립보드가 비어있으면 붙여넣기 안됨)

 

클립보드가 비어있으면 안되니까 0보다 커야하고 화면에 붙여넣으면 기존에 화면에 있던것과 클립보드에 있던것이 합쳐지는데 이 합이 S가 1000까지 이므로 1000 + 1000 인 2000보다는 작아야한다.

 

화면에 클립보드를 붙여넣었으므로 pop.0 + pop.1이 되는것이다.

if pop.1 > 0 && pop.0 + pop.1 < 2000{
            if !visited[pop.0 + pop.1][pop.1]{
                visited[pop.0 + pop.1][pop.1] = true
                queue.append((pop.0 + pop.1, pop.1, pop.2 + 1))
            }
        }

 

 

후기 : 이런 유형은 처음이라 어려웠다..

이렇게도 푸는구나 싶은문제

let n = Int(String(readLine()!))!
//화면, 클립보드, 시간
var queue: [(Int, Int, Int)] = []
var visited = Array(repeating: Array(repeating: false, count: 2000), count: 2000)

var result = 0
visited[1][0] = true
func bfs(_ start: (Int, Int, Int)){
    queue.append(start)
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0 == n {
            result = pop.2
            break
        }
        if pop.0 >= 1 && pop.0 < 2000{
            if !visited[pop.0][pop.0]{
                visited[pop.0][pop.0] = true
                queue.append((pop.0,pop.0,pop.2 + 1))
            }

            if !visited[pop.0 - 1][pop.1]{
                visited[pop.0 - 1][pop.1] = true
                queue.append((pop.0 - 1, pop.1, pop.2 + 1))
            }
        }

        if pop.1 > 0 && pop.0 + pop.1 < 2000{
            if !visited[pop.0 + pop.1][pop.1]{
                visited[pop.0 + pop.1][pop.1] = true
                queue.append((pop.0 + pop.1, pop.1, pop.2 + 1))
            }
        }


    }


}
bfs((1, 0, 0))
print(result)