[Swift Algorithm] 적록색약 BOJ #10026

문제

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

10026번: 적록색약

 

내 문제 풀이

let n = Int(readLine()!)!
var picture = [[Character]]()
var count = 0
var count2 = 0

for _ in 0..<n { picture.append(Array(readLine()!)) }

func dfs(_ x: Int, _ y: Int, _ mark: Character, _ color: Character) {
    if x < 0 || y < 0 || x >= n || y >= n || picture[x][y] == mark || picture[x][y] != color { return } // 예외
    
    picture[x][y] = mark // 이미 체크한 자리 표시해서 중복 피하기
    
    // 재귀 호출
    dfs(x+1, y, mark, color)
    dfs(x-1, y, mark, color)
    dfs(x, y+1, mark, color)
    dfs(x, y-1, mark, color)
}

// 적록색약 아닌 사람 (1차)
for i in 0..<n {
    for j in 0..<n {
        if picture[i][j] == "c" || picture[i][j] == "s" { continue }
        else {
            if picture[i][j] == "R" { dfs(i, j, "s", "R") }
            else if picture[i][j] == "G" { dfs(i, j, "s", "G") }
            else if picture[i][j] == "B" { dfs(i, j, "c", "B") }
            count += 1
        }
    }
}

// 적록색약인 사람 (2차)
for i in 0..<n {
    for j in 0..<n {
        if picture[i][j] == "f" { continue }
        else {
            if picture[i][j] == "s" { dfs(i, j, "f", "s") }
            else if picture[i][j] == "c" { dfs(i, j, "f", "c") }
            count2 += 1
        }
    }
}

print(String(count) + " " + String(count2))

👉 dfs로 풀어주었고, 적록색약이 아닌 시선을 먼저 체크한 후 적록색약일 때를 체크해주면 쉽다.

• 1차로 적록색약이 아닌 사람의 시선으로 dfs를 돌려서 영역의 개수를 구하고,
  2차로 적록색약인 사람의 시선으로 dfs를 돌려서 영역의 개수를 구해주었다.
• picture라는 배열은 주어진 그림의 색깔들을 저장했는데, picture을 var로 두고
  dfs를 돌리면서 체크를 완료한 자리는 다른 알파벳으로 바꿔서 중복을 피할 수 있게 했다.
• 먼저 1차에서는 영역을 R, G, B로 나눠서 체크하는데,
  체크하면서 R과 G의 경우에는 체크 완료한 자리를 "s"로, B는 "c"로 바꿨다.
  2차로 체크할 때는 적록색약의 입장에서 체크해야하기 때문에 이렇게 구분했다.
• 2차로 체크할 때는 picture의 모든 자리에 "s"혹은 "c"만 있을 것이다.
  따라서 s와 c로 영역을 구분해서 영역의 개수를 구해주면 된다.

 

💡 피드백

• dfs를 돌리는 for문을 두 번이나 돌려야 해서 1초 안에 문제가 돌아갈지..?가 의문이라
  풀면서 조금 걱정됐지만 잘 돌아갔다.
• 평소 dfs를 잘 쓸 줄 아는 사람이라면 모두 쉽게 풀 수 있는 문제인 것 같다.