백준 10026번 Swift 알고리즘 연습 - 적록색약_BFS

원래 BFS 문제를 다시 풀때마다 함수를 만들어내는게 꽤나 오래 걸렸는데 이젠 좀 익숙해진거 같다. 다만 은근히 문제들마다 조건이 달라서 까딱 잘못하면 조건을 만족시키기 못하는 경우가 있으니 이를 유의하는게 좋겠다.

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 다른 BFS 문제들과 비슷한 과정을 겪는다.
2. 우선 Graph를 그려주고, 움직일 수 있는 방향을 설정해준다.
3. 그리고 내가 해당 위치를 방문했는지 안했는지 visited 배열을 이용해 확인해준다.
4. 이 문제의 경우 적록색약인 경우 R과 G를 동일하게 판단해야하고
5. 적록색약이 아닌 경우 R G B를 각각의 값으로 봐주어야 하기 때문에 bfs 함수에도 이를 반영해야한다.
6. 따라서 colorWeak이 true인 경우 RG를 묶어서 한번에 이동하고
7. false인 경우는 R G B 라인을 동서남북 이동하면서 visited 표시를 남긴다.
8. 이렇게 하면 같은 값을 이루어진 이어진 구역을 찾을 수 있고 bfs 함수가 종료된 후 count + 1 해주면 각 구역의 개수를 구할 수 있다.

 

 

* 10026번

import Foundation

let n = Int(readLine()!)!
var graph = [[String]]()
var visited = [[Bool]]()
var count = [0, 0]

let dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]

for _ in 0..<n {
    graph.append(readLine()!.map{ String($0) })
    visited.append(Array(repeating: false, count: n))
}

// 적록색약이 아닌 경우
for i in 0..<n {
    for j in 0..<n {
        if !visited[i][j] {
            bfs(i, j, colorWeak: false)
            count[0] += 1
        }
    }
}

// 초기화
visited = Array(repeating: Array(repeating: false, count: n), count: n)

// 적록색약의 경우
for i in 0..<n {
    for j in 0..<n {
        if !visited[i][j] {
            bfs(i, j, colorWeak: true)
            count[1] += 1
        }
    }
}

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

func bfs(_ x: Int, _ y: Int, colorWeak: Bool) {
    var queue = [[x, y]]
    let color = graph[x][y]
    visited[x][y] = true

    while !queue.isEmpty {
        let current = queue.removeFirst()
        for i in 0..<4 {
            let nx = current[0] + dx[i]
            let ny = current[1] + dy[i]

            if 0..<n ~= nx && 0..<n ~= ny && !visited[nx][ny] {
                if colorWeak && (color == "R" || color == "G") && (graph[nx][ny] == "R" || graph[nx][ny] == "G") {
                    queue.append([nx, ny])
                    visited[nx][ny] = true
                }
                else if graph[nx][ny] == color {
                    queue.append([nx, ny])
                    visited[nx][ny] = true
                }
            }
        }
    }
}

 

 

정리(Today I Learned)

1. 이전 '현수막' 문제를 풀면서 나에게 조금 더 직관적인 코드가 어떤 것인지 고민했는데, 이번 문제에서 확실히 답을 찾은 것 같다. 컴퓨터에겐 아무런 의미가 없을지라도... 코드를 작성하는 내 입장에서 보여지는 것이 상당히 중요하기 때문에 visited 배열 설정이나 dx dy 방향 설정 등이 의미가 있는 것 같다. 앞으로도 비슷한 형태를 유지하여 문제를 풀어봐야겠다.