[Swift] 백준_적록색약(10026)

문제

 

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

 

풀이

 

색약인 사람과 색약이 아닌 사람의 답을 한 번에 구할 수 없다고 생각하여 두 번에 나눠서 구했다.

BFS로 해결했기때문에 이전의 BFS문제의 풀이 방법과 거의 동일하게 구현하였다.

 

removeAll()메서드의 시간복잡도가 O(N)인 것을 알게되어 하나의 큐를 써서 removeAll()한 뒤에 다음 반복문을 돌리는 것이 아닌 각각의 큐를 만들어주었다.

 

또한 idx를 이용해 queue[idx]가 removeFirst()보다 시간복잡도가 낮다고만 생각하여 이 방법을 주로 사용해왔었는데, 시간이 너무 오래걸려 removeFirst()를 이용해 queue.isEmpty일때까지 반복문을 돌려봤더니 시간이 엄청 단축되었다.

append()의 시간복잡도를 O(1)이라고만 생각해서 그랬던 것 같다. 물론 평균적으로는 O(1)이라고 나오지만 메모리를 재할당해야하는 경우에는 O(N)이 될 수 있다고한다.

idx를 이용했던 방법은 큐를 비우지않고 계속해서 append()하고 idx값을 이용해 값을 찾았는데, queue[idx]는 O(1)이지만 큐의 원소가 계속해서 늘어나게 되어 append()하는데에 시간이 오래걸린 것이 아닐까 생각이 든다.

 

 

 

아무튼 풀이를 보면,

 

반복문을 돌다가 visited[i][j]가 0이면 큐에 넣고 while문을 통해 큐가 빌때까지 반복해준다.

이때 상하좌우로 확인해서 visited[newX][newY]가 0이고, 현재 칸의 색과 paint[newX][newY]의 색이 동일하다면 큐에 해당 좌표를 추가해서 다시 반복문을 돌게된다.

 

색약이 아닌 사람인 경우엔 해당 칸의 색과 동일한지만 확인하면되고, 색약인 경우에는 "R"이나 "G"일땐 paint[newX][newY]가 "B"만 아니면 되고 "B"일땐 paint[newX][newY]가 "B"인지만 확인해서 큐에 추가해주면 된다.

import Foundation

let n = Int(readLine()!)!
var paint: [[String]] = []
for _ in 0..<n {
    paint.append(readLine()!.map { String($0) })
}
var visited = Array(repeating: Array(repeating: 0, count: n), count: n)
var firstQueue: [[Int]] = []
var secondQueue: [[Int]] = []
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var first = 0
var second = 0
for i in 0..<n {
    for j in 0..<n {
        if visited[i][j] == 0 {
            firstQueue.append([i,j])
            first += 1
            visited[i][j] = 1
            while !firstQueue.isEmpty {
                let current = firstQueue.removeFirst()
                for k in 0..<dx.count {
                    let newX = current[0] + dx[k]
                    let newY = current[1] + dy[k]
                    if newX < 0 || newY < 0 || newX >= n || newY >= n {
                        continue
                    }
                    if visited[newX][newY] == 1 {
                        continue
                    }
                    if paint[current[0]][current[1]] == paint[newX][newY] {
                        firstQueue.append([newX,newY])
                        visited[newX][newY] = 1
                    }
                }
            }
        }
    }
}
visited = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in 0..<n {
    for j in 0..<n {
        if visited[i][j] == 0 {
            secondQueue.append([i,j])
            visited[i][j] = 1
            second += 1
            while !secondQueue.isEmpty {
                let current = secondQueue.removeFirst()
                for k in 0..<dx.count {
                    let newX = current[0] + dx[k]
                    let newY = current[1] + dy[k]
                    if newX < 0 || newY < 0 || newX >= n || newY >= n {
                        continue
                    }
                    if visited[newX][newY] == 1 {
                        continue
                    }
                    if paint[current[0]][current[1]] == "R" || paint[current[0]][current[1]] == "G" {
                        if paint[newX][newY] == "B" {
                            continue
                        }
                    } else {
                        if paint[newX][newY] != "B" {
                            continue
                        }
                    }
                    secondQueue.append([newX,newY])
                    visited[newX][newY] = 1
                }
            }
        }
    }
}
print("\(first) \(second)")

 

____________________________________________________________________________________________________

 

시간복잡도를 확실하게 생각해서 구현해야 할 것 같다. O(1)인 것을 써도 이번 문제처럼 다른 곳에서 추가적으로 시간이 들 수도 있으므로 잘 생각하자.