[백준] (Swift) 10026번 - 적록색약 (골드5) (DFS)

골드여서 겁먹었는데 조건처리만 잘 해주면 아주 쉬운 문제였당!

 

⚫️ 문제

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

10026번: 적록색약

 

⚫️ 나의 고민,,, 풀이

문제를 읽자마자 어떻게 풀어야할지 파악했지만,, , 동시에 고민이 들었던 것이 있다. 적록색약인경우와, 적록색약이 아닌 경우를 따로 dfs를 돌려주어야할까? 그렇게 하게 된다면,,, 시간이 너무 오래걸리지 않을까? 싶었다. 그래서 코드를 어떻게 하면 깔끔하게 짤 수 있을까, DFS를 한 번만 돌리면서 두마리 토끼를 모두 잡을 수 있을지 고민했다. 

🔖 시간복잡도 먼저 띵크해보자

배열은 무조건 NxN 으로 주어진다. 그리고, N의 최대 값은 100이다. DFS 하나당 N번의 loop를 돌기 때문에 O(N)의 시간 복잡도를 갖지만, 전부 방문하면서 탐색해주어야하니까 O(N^2)의 시간복잡도를 갖는다. 최대 그럼 10000번의 loop를 돌게 되는데, 이정도는 무리 없이 돌아갈 것 같았고, DFS를 채택하기로 결정했다. (DFS를 두번 돌려도 결국 빅오표기법에선 O(N^2)이므로 두번돌려도 무리없이 돌아갈것 같았다.)

🔖 처음 생각한 방식

음,, 우선 처음에 생각한 방식은 처음에 입력받는 picture을 두가지로 저장하는 방식이었다. G과 R를 하나로 통일시킨 적록색약 전용 picture 배열과, 그냥 입력받은 picture 배열 이렇게 두가지를 만들어서, DFS를 두번 돌리는 방식을 처음에 생각했다. 근데.. 뭔가 맘에 안들어! 더 잘짜고 싶은 마음이 들었다.

🔖 고민하다가 결국 채택한 방식

고민하다가 결국 dfs를 두번 돌리기로 결정했다. 왜냐면, pictrue배열을 두개 만들었더라도, 상황에 따라 분기처리를 따로 해서 재귀를 돌려줘야했기 때문이다. 마땅히 다른 방법이 생각나지 않아서, dfs를 두번 돌리기로 했다... 그래,, dfs두번 돌려도 무리가 없도록 조건을 저렇게 주어줬겠지,, 그리고 항상 조건을 저렇게 준 이유가 있겠지! 하고 생각하면 ??? 두번 돌리는게 그래 맞겠다!!

🔖 코드 구현

main으로 돌아가는 부분에서 2중 for loop를 사용해서 모든 노드를 탐색했다. 그리고, 그 내부에서 dfs를 두번 돌렸다! 그리고, dfs 코드는 두번 작성하면 비효율적일 것 같아서, enum으로 type을 따로 만들어준 뒤, 분기처리로 type까지 함께 넘겨주었다.

dfs 내부 코드도 약간 비슷한 형태로 반복되기 때문에 따로 더 깔끔하게 짤 수 있을지 고민했지만,, 일단,, 그래 일단 여기서 끝...

⚫️ 정답코드

import Foundation

let n = Int(readLine()!)!
var picture = [[String]]()

for _ in 0..<n {
    picture.append(readLine()!.map{ String($0) })
}

var redGreenDiseaseVisited = Array(repeating: Array(repeating: false, count: n), count: n)
var nonDiseaseVisited = Array(repeating: Array(repeating: false, count: n), count: n)
var answer = [0, 0]

// 상 하 좌 우
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

enum type {
    case redGreenDisease
    case nonDisease
}

private func dfs(x: Int, y: Int, type: type) {
    switch type {
    case .redGreenDisease:
        redGreenDiseaseVisited[x][y] = true
        let now = picture[x][y]

        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]

            if nx < 0 || ny < 0 || nx >= n || ny >= n {
                continue
            }

            if now == "G" || now == "R" {
                if picture[nx][ny] == "G" || picture[nx][ny] == "R", !redGreenDiseaseVisited[nx][ny] {
                    dfs(x: nx, y: ny, type: .redGreenDisease)
                }
            } else {
                if picture[nx][ny] == now, !redGreenDiseaseVisited[nx][ny] {
                    dfs(x: nx, y: ny, type: .redGreenDisease)
                }
            }
        }

    default:
        nonDiseaseVisited[x][y] = true
        let now = picture[x][y]

        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]

            if nx < 0 || ny < 0 || nx >= n || ny >= n {
                continue
            }

            if now == picture[nx][ny], !nonDiseaseVisited[nx][ny] {
                dfs(x: nx, y: ny, type: .nonDisease)
            }
        }
    }

}

// main : 모든 노드 탐색
for i in 0..<n {
    for j in 0..<n {
        if !nonDiseaseVisited[i][j] {
            answer[0] += 1
            dfs(x: i, y: j, type: type.nonDisease)
        }

        if !redGreenDiseaseVisited[i][j] {
            answer[1] += 1
            dfs(x: i, y: j, type: type.redGreenDisease)
        }
    }
}

print("\(answer[0]) \(answer[1])")