백준 10026번 적록색약 - 스위프트(Swift) 풀이

1. 그리드의 각 칸을 그래프의 정점으로 생각한다.
2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다.
3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 구역 내의 모든 칸을 방문할 수 있다.
4. 따라서 DFS/BFS의 호출 횟수가 곧 구역의 개수이다.
5. 적록색약인 경우 그리드의 R과 G를 같은 색으로 취급해준다.

---

1. 그리드의 각 칸을 그래프의 정점으로 생각한다.

 그리드 전체를 그래프로 생각할 수 있다. 각 칸을 정점으로 둔다.

 

2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다.

 상하좌우로 인접한 칸이 같은 색이면 같은 구역이므로, 간선으로 연결해준다. 이러면 같은 구역인 정점끼리만 간선으로 연결될 것이다.

 

3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 구역 내의 모든 칸을 방문할 수 있다.

 1,2 작업을 하고 나면 그래프가 완성되고, 그래프의 한 정점에서 DFS/BFS로 탐색을 하면 해당 칸이 속하는 구역 내의 다른 모든 칸을 방문할 수 있다. 2번 작업을 해주었기 때문에 다른 구역(다른 색상)인 정점은 방문하지 않는다.

 

 

4. 따라서 DFS/BFS의 호출 횟수가 곧 구역의 개수이다.

 어떤 정점에서 DFS/BFS를 하면 해당 구역 하나를 전부 방문할 수 있다. 따라서 모든 칸을 차례로 확인하면서 아직 방문하지 않은 칸이면, 그 칸을 시작점으로 DFS/BFS를 돌려주면서 DFS/BFS의 호출 횟수를 카운트하면, 그것이 곧 구역의 개수가 된다.

 

 

5. 적록색약인 경우 그리드의 R과 G를 같은 색으로 취급해준다.

적록색약인 경우 R과 G도 간선으로 연결해주어야 한다. 그냥 간단하게 그리드에서 모든 R을 G로 만들어버리거나 G를 R로 만들어버리면 된다.

 

---

import Foundation

var N = 0
var grid = Array(repeating: Array(repeating: "", count: 102), count: 102)
var visit = Array(repeating: Array(repeating: false, count: 102), count: 102)

typealias Adjacent = (dr: Int, dc: Int)

func dfs(row: Int, col: Int) {
    visit[row][col] = true
    
    let color = grid[row][col]
    
    let adjacents: [Adjacent] = [(1,0), (-1,0), (0,1), (0,-1)]
    for adj in adjacents {
        let adjRow = row + adj.dr
        let adjCol = col + adj.dc
        
        let adjColor = grid[adjRow][adjCol]
        let adjVisit = visit[adjRow][adjCol]
        
        if !adjVisit && adjColor == color {
            dfs(row: adjRow, col: adjCol)
        }
    }
}

func countCC() -> Int {
    var count = 0
    
    for row in 1...N {
        for col in 1...N {
            if !visit[row][col] {
                dfs(row: row, col: col)
                count += 1
            }
        }
    }
    
    return count
}

func makeColorBlindness() {
    for i in 0..<102 {
        for j in 0..<102 {
            if grid[i][j] == "G" { grid[i][j] = "R" }
        }
    }
}

func resetVisit() {
    visit = Array(repeating: Array(repeating: false, count: 102), count: 102)
}

func solution() {
    N = Int(readLine()!)!
    
    for i in 1...N {
        let input = readLine()!
        input.enumerated().forEach { grid[i][$0 + 1] = String($1) }
    }
    
    let notColorBlindness = countCC()
    
    makeColorBlindness()
    resetVisit()
    
    let colorBlindness = countCC()
    
    print("\(notColorBlindness) \(colorBlindness)")
}

solution()