[백준/Swift] 10026 : 적록색약

안녕하세요!

---

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

10026번: 적록색약

---

간단한 문제 해석으로 시작하겠습니다

적록색약을 가진 사람은 빨간색과 초록색을 같은 색으로 인식합니다.

 

주어진 image이미지는 N x N 형태로 이루어져 있습니다. 

구역 을 구해야 하는데, 같은 색상이 상 하 좌 우 인접해 있는 경우 두 글자를 같은 구역에 속한다고 표현합니다.

이때 적록색약의 경우 빨간색과 초록색을 같은색으로 인식하기에 이에 대한 조건을 걸어주셔야 합니다.

---

이 문제의 경우 모든 image 구간을 탐색하면서 bfs보단 dfs로 탐색하는 것이 좋다고 생각해 dfs 탐색을 통해 

특정한 구역을 모두 탐색할 경우 특정 색 "R, G , B" -> "V"(Visited)로 바꾸었습니다.  

일반적인 사진 탐색은 그냥 dfs를 구현하면 되는데,

적록색약의 경우,

특정 좌표에 색이 "R" 이나 "G"일 때 탐색을 계속하도록 하는 조건을 걸어야해서 dfs함수를 총 2개 만들었습니다...(같은 코드가 몇갠지;;ㅠㅠㅠ)

구현을 성공적으로 하고, 다른 분들의 코드를 참고했고, 주어진 String에서 특정 char -> char로 바꾸는 메서드를 알게 되었습니다.

//일반적인 사람
func dfs(currentX x : Int, currentY y : Int, image : inout[[String]]){
    var stack = [(Int,Int)]()
    let char = image[y][x]
    stack.append((x,y))
    while(stack.count != 0){
        let coord = stack.popLast()!
        for (dx,dy) in direction{
            let nx = dx + coord.0
            let ny = dy + coord.1
            if nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1 {
                continue
            }
            if image[ny][nx] == char {
                stack.append((nx,ny))
                image[ny][nx] = "V"
            }
        }

    }
}
//적록색약
func _RG_dfs(currentX x: Int, currentY y : Int){
    var stack = [(Int,Int)]()
    let char = RGImage[y][x]
    var rgWeakness = false
    if char == "R" || char == "G" {
        rgWeakness = true
    }
    stack.append((x,y))
    while(stack.count != 0){
        let coord = stack.popLast()!
        for (dx,dy) in direction{
            let nx = dx + coord.0
            let ny = dy + coord.1
            
            if nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1 {
                continue
            }
            if rgWeakness == true{
                if RGImage[ny][nx] == "R" || RGImage[ny][nx] == "G"{
                    stack.append((nx,ny))
                    RGImage[ny][nx] = "V"
                }
            }else if RGImage[ny][nx] == char {
                stack.append((nx,ny))
                RGImage[ny][nx] = "V"
            }
        }

    }
}

 

그래서 더 이상 _RG_dfs() 함수는 필요가 없어졌습니다.

적록색약 사람은 R == G 같은 색으로 보기에 두가지 글자중 한가지 글자로 변환하게 된다면 dfs()탐색만 하면 되기 때문입니다.

 

그래서 다음은

String.replacingOccurrences(of:with:) 메서드를 사용한 코드입니다.

 

import Foundation

var n = Int(readLine()!)!
var direction = [(-1,0),(1,0),(0,1),(0,-1)]
var image = Array(repeating: [String](), count: n)
/**
 * imgae는 일반인의 시각에서 그룹의 방문을 탐색할 때 사용.
 * RGImage는 적록색약
 * 방문했을 경우 특정 좌표의 명암도가 "R,G,B" - > "V"
 */
var RGImage = image
var rImg = 0
var rRGImg = 0
/**
 * String의 특정 char를 다른 특정 char로 변환하는 함수
 * replacingOccurrences(of:with:)
 * 이때 이 함수를 사용한 문자열은 그대로고, of:with: 조건이 반영된 문자열은 반환이 된다!
 */
for y in 0..<n{
    var colors = readLine()!
    image[y] = colors.map{String($0)}
    colors = colors.replacingOccurrences(of: "G", with: "R")
    RGImage[y] = colors.map{String($0)}
}
/**
 * 이미지에서 모든 구간에 대해 탐색!
 * 이때 dfs를 통해 방문했을 경우 "V"로 바꾸어 방문 완료 표시!
 */
for y in 0..<n{
    for x in 0..<n{
        if image[y][x] != "V"{
            dfs(currentX: x, currentY: y, image: &image)
            rImg += 1
        }
        if RGImage[y][x] != "V"{
            dfs(currentX: x, currentY : y, image: &RGImage)
            rRGImg += 1
        }
    }
}
print("\(rImg) \(rRGImg)")

/**
 * 맨 처음 방문하지 않은 (x,y) 좌표의 문자를 char에 저장하고,
 * char를 기준으로 탐색해야 할 이미지의 색이 char이라면 stack에 저장! -> 탐색의 반복!!
 */
func dfs(currentX x : Int, currentY y : Int, image : inout[[String]]){
    var stack = [(Int,Int)]()
    let char = image[y][x]
    stack.append((x,y))
    while(stack.count != 0){
        let coord = stack.popLast()!
        for (dx,dy) in direction{
            let nx = dx + coord.0
            let ny = dy + coord.1
            if nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1 {
                continue
            }
            if image[ny][nx] == char {
                stack.append((nx,ny))
                image[ny][nx] = "V"
            }
        }

    }
}