백준 1941번
https://www.acmicpc.net/problem/1941

문제

---

생각하기

---

• 백트래킹 조합 문제이다.

  • 25C7 조합이다

• 여러가지 풀이 방법이 나오는 좋은 문제라는 평가가 많다

• 여기서는 적용하지 못했지만, depth가 4만 되어도 사실상 이 조합으로 칠공주를 결성할 수 있는지 없는지 판단 할 수 있기 때문에 가지치기에 적용하여 시간을 줄 일 수 있다.

• HashSet을 사용해서 이미 만들어진 조합인지 평가하는데, 사실 좋은 방법이라고 보기는 어려운 것 같다. Set자체가 넣고 확인하고 하는데 시간을 많이 잡아먹기 때문.

동작

코드

---

Kotlin

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 5
private var ans = 0

private var map = Array(N) { CharArray(N) }
private var isVisited = Array(N) { BooleanArray(N) }
private var checkArray = CharArray(7)
private var dirX = arrayOf(-1, 1, 0, 0)
private var dirY = arrayOf(0, 0, -1, 1)

private var set = HashSet<String>()


fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    input()

    DFS(0)

    sb.append(ans)
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun DFS(depth: Int) {
    if (depth == 7) {
        var cnt = 0
        val sb = StringBuilder()

        for (i in 0 until N) {
            for (j in 0 until N) {
                if (isVisited[i][j]) {
                    sb.append(i).append(j)
                    if (map[i][j] == 'S') {
                        cnt++
                    }
                }
            }
        }

        if (cnt >= 4 && !set.contains(sb.toString())) {
            set.add(sb.toString())
            ans++
            return
        }

        return
    }

    for (i in 0 until N) {
        for (j in 0 until N) {

            if (depth != 0) {
                var cnt = 0
                for (k in 0 until 4) {
                    val nextX = dirX[k] + i
                    val nextY = dirY[k] + j

                    if (!rangeCheck(nextX, nextY)) continue
                    if (isVisited[nextX][nextY]) cnt++
                }
                if (cnt == 0) continue
            }

            if (isVisited[i][j]) continue

            isVisited[i][j] = true
            // 백트래킹의 핵심은 가지치기
            // 25C7 조합
            checkArray[depth] = map[i][j]
            DFS(depth + 1)
            isVisited[i][j] = false
        }
    }
} // End of DFS

private fun rangeCheck(nextX: Int, nextY: Int): Boolean {
    return nextX < N && nextX >= 0 && nextY < N && nextY >= 0
} // End of rangeCheck

private fun input() {
    for (i in 0 until N) {
        map[i] = br.readLine().toCharArray()
    }
} // End of input