[알고리즘] DFS/Quad Tree로 구성되어 있는 문자열에 대한 해상도 구하기

해당 문제는 프로그래머스나, 백준과 같은 Judge Site 에서 확인한 것이 아닌 개인적인 경로로 본 알고리즘이다.

굉장히 재밌게 풀었던 문제여서 기록을 해둔다.

(일반적인 DFS가 아닌 문자열에 대한 DFS, 그리고 그림을 그리는 과정? 에서 재밌게 느꼈다.)

 

먼저 문제에 대한 설명을 하자면 해상도가 1024인 사각형이 있다고 하자.

그 사각형에 대해 4분할하여 우선순위를 배열하고, 4분할된 사각형에 대해 다시 4분할을 진행하는 문제다.

우선순위 표시 및 사각형 구조에 대한 표시

 

문자열은 Black(B) / White(W) / P(Node) 로 나뉘어 있고, B/W/P에 대해서는 해당 사각형이 검정색인지, 하얀색인지, 노드인지에 대한 값이다.

P는 큰 사각형에서 작은 사각형으로 들어갈 때 쓰이는 구분자이다.

예시)
큰 사각형(1번만 있는 이미지-1/1) 에서 1/2/3/4로 쪼개진 곳(1/4)으로 들어가려면 p 구분자가 하나 필요
그 안에서 1번에 대해 또 쪼개진 사각형(1/16)으로 들어가기 위해선 p 구분자가 하나 필요)

2개의 문자열이 주어지는데 이 2개에 대해 검정색으로 표시되는 곳에 대한 해상도만 찾아내면 되는 알고리즘이다.

예시)
s1 = ppwwwbpbbwwbw
s2 = pwbwpwwbw

s1(ppwwwb...)에 대해서 해석해보자면, 큰 사각형 내에서 4분할된 사각형으로 들어가고(p) 4분할된 사각형 내에서 4분할을 시켜 들어가고(p) 작은 4분할된 사각형 내에서는 wwwb 에 대한 값을 가진 다는 것 이다.

이런식으로 해석하면 아래와 같은 이미지가 된다.

 

s1 = ppwwwb 해석 이미지

 

s1에 대해 전체를 해석해보자면 아래와 같은 이미지가 된다.

s1 전체 해석(빨간색은 pwwwb, 주황색은 pbbww, 노란색은 b, 초록색은 w)

이제 s2에 대해 해석해보면 아래와 같은 이미지가 나온다.

s2 전체해석

위 두개의 이미지를 합치면 아래와 같은 이미지가 나온다.

s1 + s2

여기서 검정색인 사각형에 대해 해상도 합을 계산해보면 640이다.(검정색 블럭이 10개)

 

즉 ppwwwbpbbwwbw + pwbwpwwbw = 640 이라는 해석이 나온다.

 

다른 예시를 들어보자.

예시)
s1 = b
s2 = w

위 예시를 예로 들면 큰 사각형 하나는 전부 다 검은색이고, 다른 큰 사각형은 전부 다 흰색이다.

b + w  = 1024가 된다.

 

위 문제를 풀어봤는데 재미있엇다.

DFS를 이용하면 쉽게 풀 수 있다.

문제를 해결 할 때 DFS를 이용하여 Map을 그린다고 생각하면 풀기 쉽다.

(Map을 그리지 않고 풀라하다가 시간이 많이 소요된 기억이 있다.)

 

결국 검정색인 것에 대해서만 구하면 되는 작업이니 효율을 따지자면 Map 따로 그리지 않아도 쉽게 풀 수 있을 것 같다.

 

아래는 따로 Map을 그려 푼 방법이다.

(Map 그리는 소스때문에 더러워져서 그리지 않고 푸는게 더 이쁠 것 같다.)

package ktPrj
 
var img = Array<IntArray>(4) { IntArray(4) }
fun main() {
    val s1 = "ppwwwbpbbwwbw"
    val s2 = "pwbwpwwbw"
 
    val s1Visited: BooleanArray = BooleanArray(s1.length) { false }
    drawImg(s1, 0, s1Visited, 0)
 
    val s2Visited: BooleanArray = BooleanArray(s1.length) { false }
    drawImg(s2, 0, s2Visited, 0)
 
    var r = 0
    img.forEach { it ->
        r += it.sumBy { it }
    }
 
    println("$r, ${r*64}")
}
 
// pwwwbpbbwwbw
// wbwpwwbw
// DFS 재귀함수.
fun drawImg(s: String, depth: Int, visited: BooleanArray, direction: Int) {
    val charAry = s.toCharArray()
 
    for (i in charAry.indices) {
        val char = charAry[i]
        if (visited[i])
            continue
 
        visited[i] = true
 
        if (char == 'p') {
            drawImg(s, depth + 1, visited, direction)
        } else {
            if (depth == 2) {
                for ((detailDirection, j) in (i until i + 4).withIndex()) {
                    visited[j] = true
                    quadImg(charAry[j], direction, detailDirection, depth)
                }
                drawImg(s, depth - 1, visited, direction + 1)
            } else {
                quadImg(charAry[i], direction, 0, depth)
                drawImg(s, depth, visited, direction + 1)
            }
        }
    }
}
 
/**
 * 실제로 사각형 별로 우선순위에 따라 그려주는 작업.
 */
fun quadImg(color: Char, direction: Int, detailDirection: Int, depth: Int) {
    if (color == 'w') return
 
    if (depth == 0) {
        for(i in 0..3) {
            for(j in 0..3) {
                img[i][j] = 1
            }
        }
    } else {
 
        if (direction == 0) {
            if (depth == 1) {
                for (i in 0..1) {
                    for (j in 2..3) {
                        img[i][j] = 1
                    }
                }
            } else if (depth == 2) {
                if (detailDirection == 0) {
                    img[0][3] = 1
                } else if (detailDirection == 1) {
                    img[0][2] = 1
                } else if (detailDirection == 2) {
                    img[1][2] = 1
                } else if (detailDirection == 3) {
                    img[1][3] = 1
                }
            }
        } else if (direction == 1) {
            if (depth == 1) {
                for (i in 0..1) {
                    for (j in 0..1) {
                        img[i][j] = 1
                    }
                }
            } else if (depth == 2) {
                if (detailDirection == 0) {
                    img[0][1] = 1
                } else if (detailDirection == 1) {
                    img[0][0] = 1
                } else if (detailDirection == 2) {
                    img[1][0] = 1
                } else if (detailDirection == 3) {
                    img[1][1] = 1
                }
            }
        } else if (direction == 2) {
            if (depth == 1) {
                for (i in 2..3) {
                    for (j in 0..1) {
                        img[i][j] = 1
                    }
                }
            } else if (depth == 2) {
                if (detailDirection == 0) {
                    img[3][1] = 1
                } else if (detailDirection == 1) {
                    img[3][0] = 1
                } else if (detailDirection == 2) {
                    img[2][0] = 1
                } else if (detailDirection == 3) {
                    img[2][1] = 1
                }
            }
        } else if (direction == 3) {
            if (depth == 1) {
                for (i in 2..3) {
                    for (j in 2..3) {
                        img[i][j] = 1
                    }
                }
            } else if (depth == 2) {
                if (detailDirection == 0) {
                    img[2][3] = 1
                } else if (detailDirection == 1) {
                    img[2][2] = 1
                } else if (detailDirection == 2) {
                    img[3][2] = 1
                } else if (detailDirection == 3) {
                    img[3][3] = 1
                }
            }
        }
    }
}