백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

조건에 맞지 않는 후보는 제외하면서 탐색하여 불필요한 재귀 호출을 줄일 수 있다

BOJ 

15649. N과 M (1)

순서가 있는 숫자 조합 출력하기

 

arr : 출력할 숫자를 담을 배열

isUsed : 현재 사용된 숫자를 구분하기 위한 배열 (isUsed[2] = 1 : 숫자 2는 이미 조합에 사용되었다)

k: 현 인덱스, 몇번째 숫자까지 채웠는지 알 수 있다

 

구현

base condition : k == m 

• 그동안 arr에 모은 숫자를 출력한다

backtracking

•  isUsed[i] == 1 : 사용된 숫자라면 제외한다
•   isUsed[i] == 0 : 아직 사용하지 않은 숫자일 경우 
  • arr에 추가 arr[k] = i, 사용했다는 표시 isUsed[i] = 1
  • 수열에 추가할 다음 수를 탐색한다 func(k+1)
  • func(k+1)이 끝났다는 것은 현재에 대한 모든 탐색을 마쳤다는 뜻(다음 탐색에서 숫자를 사용할 수 있도록 isUsed[i] = 0으로 변경해준다)

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

private var n = 0
private var m = 0
private var isUsed = IntArray(10)
private var arr = IntArray(10)
private val sb = StringBuilder()

private fun func(k: Int) {
    if (k == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in 1..n) {
        if (isUsed[i] == 1) continue
        arr[k] = i
        isUsed[i] = 1
        func(k + 1)
        isUsed[i] = 0
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()

    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

9663. N-Queen

퀸의 공격 방향은 상,하,좌,우, 대각선이다

이미 존재하는 퀸과 같은 열에 있지 않고, 같은 대각선 상에 있지 않으면 새로운 퀸을 놓을 수 있다

1. 첫번째 행에 퀸을 둔다

2. 다음 행에서 퀸을 둘 수 있는 위치를 찾는다 (같은 열 x, 같은 대각선 x)

-> 둘 수 있는 위치가 없으면 1로 돌아간다 (백트래킹)

-> 둘 수 있는 위치가 있다면 다음 행에 대하여 2를 수행한다

 

import java.io.*
import kotlin.math.abs

private var n = 0
private var cnt = 0
private val board = IntArray(15)

fun nQueen(row: Int) {
    if (row == n) {
        cnt++
        return
    }

    for (col in 0 until n) {
        board[row] = col  // 퀸이 놓인 열의 위치 저장
        // 퀸을 둘 위치를 찾았기 때문에 다음 퀸에 대하여 nQueen 수행한다
        if (promising(row)) {
            nQueen(row + 1)
        }
    }
}

// 같은 대각선, 열에 놓여있는지 검사한다
fun promising(row: Int): Boolean {
    for (i in 0 until row) {
        if (board[row] == board[i] || row - i == abs(board[row] - board[i]))
            return false
    }

    return true
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    n = readLine().toInt()
    nQueen(0)
    print(cnt)
}

 

 

1182. 부분수열의 합

모든 부분수열의 합을 구하고 그중 합이 S와 같은 경우의 수를 구하는 문제

수열에서 각 숫자를 더하거나 더하지 않거나 해서 모든 부분수열의 합을 구할 수 있다

문제에서 크기가 양수인 부분수열만 해당한다고 했기 때문에 모든 숫자를 더하지 않는 공집합은 제외한다

import java.util.*
import java.io.*

private var n = 0
private var s = 0
private val arr = IntArray(21)
private var cnt = 0

private fun func(k: Int, cur: Int) {
	//모든 수에 대해 (더할지 말지)선택을 마쳤다면 탐색 완료
    if (k == n) {
        if (cur == s) {
            cnt++
        }
        return
    }

	// k번째 원소를 더하지 않는 경우
    func(k+1, cur)
    // k번째 원소를 더하는 경우
    func(k+1, cur + arr[k])
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    s = st.nextToken().toInt()

    st = StringTokenizer(readLine())
    repeat(n) {
        arr[it] = st.nextToken().toInt()
    }

    func(0, 0)
    if (s == 0) cnt--
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write("$cnt")
    bw.close()
}

문제를 이해하지 못해서 고생했다 

 

참고

 

기본 문제 풀기

15650. N과 M(2)

63분

고른 수열은 오름차순이어야 하는 조건이 있었다(1을 골랐다면 그뒤에 오는 수는 1보다 커야 한다)

import java.io.*
import java.util.*

private var n = 0
private var m = 0
private val isUsed = IntArray(10) { 0 }
private val arr = IntArray(10)
private val sb = StringBuilder()

private fun func(curIdx: Int, start: Int) {
    if (curIdx == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in start..n) {
        if (isUsed[i] == 1) continue
        arr[curIdx] = i
        isUsed[curIdx] = 1
        func(curIdx + 1, i+1)
        isUsed[curIdx] = 0
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()

    func(0, 1)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

아무래도 재귀를 다 이해하지 못했나보다

방법은 맞았는데 구현을 제대로 못했다

 

15651. N과 M(3)

10분

같은 수를 여러번 골라도 되기 때문에 제외 조건이 없어서 다른 n과m 문제보다 쉬웠다

import java.io.*
import java.lang.StringBuilder
import java.util.*

private var n = 0
private var m = 0
private val arr = IntArray(10)
private val sb = StringBuilder()

private fun func(curIdx: Int) {
    if (curIdx == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in 1..n) {
        arr[curIdx] = i
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()

    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

15652. N과M(4)

13분

조건: 오름차순 수열일 것 

예시: 현재 1, 2 를 선택했다면 다음 수로 2보다 작은 것은 선택할 수 없다

작은 수가 올 경우 제외시키는 방식으로 구현

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private val arr = IntArray(10)
private val sb = StringBuilder()

private fun func(curIdx: Int) {
    if (curIdx == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in 1..n) {
        if (curIdx != 0 && arr[curIdx-1] > i) continue
        arr[curIdx] = i
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15654. N과 M(5)

36분

처음에 이전 숫자와 다음 수를 비교해서 이전 수가 더 클 경우 뒤로 돌아가도록 구현하려고 했는데

그럴 필요가 없이 먼저 정렬을 하면 탐색이 수월하다 

쓸데없는 구현을 하느라 시간이 좀 더 걸렸다

import java.io.*
import java.lang.StringBuilder
import java.util.*

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val isUsed = IntArray(10)
private val sb = StringBuilder()

private fun func(curIdx: Int) {
    if (curIdx == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in 0 until n) {
        if (isUsed[i] == 1) continue
        arr[curIdx] = numbers[i]
        isUsed[i] = 1
        func(curIdx+1)
        isUsed[i] = 0
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    for (i in 0 until n) {
        numbers[i] = st.nextToken().toInt()
    }
    numbers.sort()

    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15655. N과 M(6)

11분

1. 정렬

2. 탐색 - 중복 체크, 이전 수보다 작은거나 같으면 탐색 중지

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val sb = StringBuilder()
private val arr = IntArray(10)
private val isUsed = IntArray(10)

private fun func(curIdx: Int) {
    if (curIdx == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in numbers.indices) {
        if (isUsed[i] == 1) continue
        if (curIdx != 0 && arr[curIdx-1] >= numbers[i]) continue
        arr[curIdx] = numbers[i]
        isUsed[i] = 1
        func(curIdx+1)
        isUsed[i] = 0
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())

    for (i in 0 until n) {
        numbers[i] = st.nextToken().toInt()
    }

    numbers.sort()

    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15656. N과 M(7)

9분

같은 수 여러 번 사용 가능(사용체크 필요x), 사전 순(정렬 필요)

import java.util.*
import java.io.*
import java.lang.StringBuilder


private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val sb = StringBuilder()

private fun func(curIdx: Int) {
    if (curIdx == m) {
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in numbers.indices) {
        arr[curIdx] = numbers[i]
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()

    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    repeat(n) {
        numbers[it] = st.nextToken().toInt()
    }
    numbers.sort()

    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15657. N과 M(8)

8분

정렬 필요, 같은 수 여러 번 고르기 가능

고른 수열은 비내림차순 (앞에 1이 왔으면 다음에 1보다 작은 수는 올 수 없다)

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val sb = StringBuilder()

private fun func(curIdx: Int) {
    if (curIdx == m) {  // 자릿수 다 채웠다면
        for(i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in numbers.indices) {
        // 비내림차순을 위한 조건 설정
        if (curIdx != 0 && arr[curIdx-1] > numbers[i]) continue
        // 값 추가
        arr[curIdx] = numbers[i]
        // 다음 탐색 진행
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    repeat(n) {
        numbers[it] = st.nextToken().toInt()
    }

    // 사전 순 증가를 위한 정렬
    numbers.sort()

    func(0)
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

15663. N과 M(9)

1시간 25분 

중복 수열 여러 번 출력 불가, 사전 순으로 출력 

일단 set을 사용해서 처음에 중복제거를 하려고 했다가 문제를 다시 읽고 그렇게 하면 안된다는 걸 알았다

그러다 마지막에 set으로 중복제거를 해야겠다는 생각을 떠올리는데 조금 걸렸다

본격적으로 헷갈린 부분은 중간에 중복 확인하는 부분인데 인덱스를 잘못써서 답이 안나오고 있던 거였다

나한테 꽤 어렵게 느껴지는 문제였는데 포기하지 않고 풀어서 맞추기까지 해서 뿌듯하다

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val set = mutableSetOf<String>()
private val isUsed = IntArray(10)

private fun func(curIdx: Int) {
    if (curIdx == m) {
        val sb = StringBuilder()
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        set.add(sb.toString())
        return
    }

    for (i in numbers.indices) {
        if (isUsed[i] == 1) continue
        arr[curIdx] = numbers[i]
        isUsed[i] = 1
        func(curIdx+1)
        isUsed[i] = 0
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    repeat(n) {
        numbers[it] = st.nextToken().toInt()
    }

    numbers.sort()
    func(0)

    val sb = StringBuilder()
    set.forEach {
        sb.append("$it\n")
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15664.  N과 M(10)

12분

9 문제에서 약간 변형된 문제

비내림차순 수열이어야 하기 때문에 앞에 있는 수보다 뒤에 있는 수가 더 커야 한다

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val set = mutableSetOf<String>()
private val isUsed = IntArray(10)

private fun func(curIdx: Int) {
    if (curIdx == m) {
        val sb = StringBuilder()
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        set.add(sb.toString())
        return
    }

    for (i in numbers.indices) {
        if (isUsed[i] == 1) continue
        if (curIdx != 0 && arr[curIdx-1] > numbers[i]) continue
        arr[curIdx] = numbers[i]
        isUsed[i] = 1
        func(curIdx+1)
        isUsed[i] = 0
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    repeat(n) {
        numbers[it] = st.nextToken().toInt()
    }
    numbers.sort()
    func(0)

    val sb = StringBuilder()
    set.forEach {
        sb.append("$it\n")
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15665.  N과 M(11)

7분 30초

같은 수 여러 번 고르기 가능, 같은 수열은 출력 불가

앞에 두문제보다 11번이 더 쉬운 느낌이다

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val set = mutableSetOf<String>()

private fun func(curIdx: Int) {
    if (curIdx == m) {
        val sb = StringBuilder()
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        set.add(sb.toString())
        return
    }

    for (i in numbers.indices) {
        arr[curIdx] = numbers[i]
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    repeat(n) {
        numbers[it] = st.nextToken().toInt()
    }

    numbers.sort()
    func(0)

    val sb = StringBuilder()
    set.forEach {
        sb.append("$it\n")
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

 

15666.  N과 M(12)

6분 50초

드디어 N과 M 마지막 문제

같은 수 여러 번 고르기 가능, 비내림차순 수열 (7 1 불가능)

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var n = 0
private var m = 0
private lateinit var numbers: IntArray
private val arr = IntArray(10)
private val set = mutableSetOf<String>()

private fun func(curIdx: Int) {
    if (curIdx == m) {
        val sb = StringBuilder()
        for (i in 0 until m) {
            sb.append("${arr[i]} ")
        }
        set.add(sb.toString())
        return
    }

    for (i in numbers.indices) {
        if (curIdx != 0 && arr[curIdx-1] > numbers[i]) continue
        arr[curIdx] = numbers[i]
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    numbers = IntArray(n)

    st = StringTokenizer(readLine())
    repeat(n) {
        numbers[it] = st.nextToken().toInt()
    }

    numbers.sort()
    func(0)

    val sb = StringBuilder()
    set.forEach {
        sb.append("$it\n")
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write(sb.toString())
    bw.close()
}

6603.  로또

21분

N과 M 문제들과 비슷해서 푸는데 어렵지 않았다

k개의 숫자로 이루어진 수열에서 6개의 숫자를 고르는 경우를 구하는 문제

숫자를 오름차순으로 나타내야 하기 때문에 다음에 오는 수가 앞에 오는 수보다 크도록 조건을 설정해주었다

import java.util.*
import java.io.*

private var k = 0
private lateinit var s: IntArray
private val sb = StringBuilder()
private val arr = IntArray(10)

private fun func(curIdx: Int) {
    if (curIdx == 6) {
        for (i in 0 until 6) {
            sb.append("${arr[i]} ")
        }
        sb.append("\n")
        return
    }

    for (i in 0 until k) {
        if (curIdx != 0 && arr[curIdx - 1] >= s[i]) continue
        arr[curIdx] = s[i]
        func(curIdx+1)
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st: StringTokenizer

    while (true) {
        st = StringTokenizer(readLine())
        k = st.nextToken().toInt()
        if (k == 0) break

        s = IntArray(k)

        for (i in 0 until k) {
            s[i] = st.nextToken().toInt()
        }

        func(0)
        sb.append("\n")
    }

    bw.write(sb.toString())
    bw.close()
}

 

1941.  소문난 칠공주

 

bfs와 backtraking을 사용해야 한다는 건 알겠는데 어떻게 써야하는지는 생각 못했다

한시간 넘게 고민해보다가 풀이를 봤는데 역시 어렵다

칠공주인지 뭔지 풀기 싫은데 이젠 다음 단원으로 넘어가고 싶기 때문에 이해하고 넘어가야겠다

 

1. 25명의 학생 중 7명을 뽑는다

2. 뽑은 7명의 학생 중 이다솜파가 과반수 이상인지 확인한다

3. 7명이 모두 인접해 있는지 확인한다

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val arr = Array(5) { CharArray(5) }
private val visited = BooleanArray(25) { false }
private lateinit var adjVisited: BooleanArray
private val dx = arrayOf(1, -1, 0, 0)
private val dy = arrayOf(0, 0, -1, 1)
private var answer = 0
private val selected = IntArray(7) { -1 }

// 25명 중 7명 뽑기
private fun combination(cnt: Int, start: Int, sCnt: Int) {
    if (cnt == 7) {
        if (sCnt >= 4) {
            if (check())
                answer++
        }
        return
    }

    for (i in start until 25) {
        visited[i] = true

        selected[cnt] = i
        if (arr[i/5][i%5] == 'S') combination(cnt+1, i+1, sCnt+1)
        else combination(cnt+1, i+1, sCnt)

        visited[i] = false
    }
}

// 뽑은 7명이 인접한지 bfs 탐색
private fun check(): Boolean {
    adjVisited = BooleanArray(25) { false }
    val q = ArrayDeque<Int>()
    q.add(selected[0])
    var cnt = 1

    while (q.isNotEmpty()) {
        val cur = q.remove()
        adjVisited[cur] = true

        for (dir in 0 until 4) {
            val nx = (cur / 5) + dx[dir]
            val ny = (cur % 5) + dy[dir]

            val idx = nx * 5 + ny
            if (nx !in 0..4 || ny !in 0..4) continue
            if (adjVisited[idx] || !visited[idx]) continue

            cnt++
            adjVisited[idx] = true
            q.add(idx)
        }
    }

    return cnt == 7
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st: StringTokenizer
    for (i in 0 until 5) {
        st = StringTokenizer(readLine())
        st.nextToken().forEachIndexed { j, c ->
            arr[i][j] = c
        }
    }

    combination(0, 0, 0)
    print("$answer")
}

 

 

 

16987.  계란으로 계란치기

분