BOJ-10026 적록색약 Swift

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

내가 푼 풀이

- 해당 그림이 주어지면, 색의 구역의 수를 출력한다.

- 적록색약은 R,G 를 구분하지못하므로, 그래프를 탐색할 때, R과G는 같다고 판단하고 탐색한다.

- 단순히 구역의 수를 구하는 문제이므로 BFS, DFS 둘다 사용 가능하지만, DFS를 사용했다.

 

import Foundation

var n = Int(readLine()!)!
var arr = [[String]]()
var result = [Int]()

// dif 는 적록색약인지 판단
var dif = false
// x y 방향
var dx = [1,0,-1,0]
var dy = [0,1,0,-1]

// 그립을 배열에 입력
for i in 0..<n {
    var input = Array(readLine()!).map{ String($0) }
    arr.append(input)
}

// 결과 두가지 호출을 위한 result 배열
// 단순히 구역의 수를 구하기위하므로 DFS 이용
while result.count != 2 {
    var needVisitQueue = [(x: Int, y: Int)]()
    var count = 0
    var copyArr = arr
    // 정상인 사람의 구역 수 를 넣으면 색약인사람을 검사
    if result.count == 1 {
        dif = true
    } else {
        dif = false
    }
    // 정상인 사람의 구역의 개수 구하기
    if !dif {
        for i in 0..<copyArr.count {
            for j in 0..<copyArr.count {
                if copyArr[i][j] == "X" { continue }
                needVisitQueue.append((x: j, y: i))
                var check = copyArr[i][j]
                while !needVisitQueue.isEmpty {
                    var node = needVisitQueue.removeLast()
                    copyArr[node.y][node.x] = "X"
                    
                    for k in 0..<4 {
                        var cx = node.x + dx[k]
                        var cy = node.y + dy[k]
                        
                        if (cx >= 0 && cx < n) && (cy >= 0 && cy < n) {
                            if copyArr[cy][cx] == check {
                                needVisitQueue.append((x: cx, y: cy))
                            }
                        }
                    }
                }
                count += 1
            }
        }
        result.append(count)
    } else {
        // 적록색약인 사람의 구역의 개수 구하기
        for i in 0..<copyArr.count {
            for j in 0..<copyArr.count {
                if copyArr[i][j] == "X" { continue }
                needVisitQueue.append((x: j, y: i))
                var check = copyArr[i][j]
                while !needVisitQueue.isEmpty {
                    var node = needVisitQueue.removeLast()
                    copyArr[node.y][node.x] = "X"
                    
                    for k in 0..<4 {
                        var cx = node.x + dx[k]
                        var cy = node.y + dy[k]
                        
                        if (cx >= 0 && cx < n) && (cy >= 0 && cy < n) {
                            if check == "R" || check == "G" {
                                if copyArr[cy][cx] == "R" || copyArr[cy][cx] == "G" {
                                    needVisitQueue.append((x: cx, y: cy))
                                }
                            } else if copyArr[cy][cx] == check {
                                needVisitQueue.append((x: cx, y: cy))
                            }
                        }
                    }
                }
                count += 1
            }
        }
        result.append(count)
    }
}

print(result.map{String($0)}.joined(separator: " "))