백트래킹이란

728x90

💡 백트래킹은 그래프를 순회하면서 값을 찾는 중 막힐 경우 다시 되돌아가서 해를 찾는 기법을 말합니다.

이때 해를 찾는 도중에 해당 그래프 경로에 해가 존재하지 않게 될 경우 탐색하지 않는 것도 백트래킹의 일종이라고 합니다. → 전문용어로는 가지치기 라고 해요

가지치기를 통해서 더이상 탐색하지 않아야 하는 경우를 줄여 코드를 효율적으로 작성할 수 있습니다.

알고리즘 문제를 풀때 문제에 원하는 조합을 만들고 문제에서 원하는 답을 고르는 경우가 존재합니다.

만드는 조합이 크지 않고 시간이 충분하다고 생각이 들면 이러한 경우 for문만으로 표현하기 어렵고 이때 그래프 탐색 개념을 활용하고 백트래킹을 이용하여 문제를 해결할 수 있습니다.

그래프 탐색 문제 같은 경우 문제푸는 요령(bfs, dfs)

트리를 직접 그려보고 필요한 가지와 노드, 그래프 높이가 어느 정도 되는지 생각한다.
본인이 생각한 그래프를 코드로 구현하는 연습을 한다.
2-1) 가지의 개수 = 재귀함수 호출의 개수
2-2) 재귀함수 리턴 시점 → 문제에서 요구하는 조건

ex) N이 주어졌을 때, N자리 2진수를 구하는 방법

💡 N을 입력받았을때, N자리 2진수를 모두 출력하시오 예를 들어 N이 2일 경우 01,01,10,11 경우가 있을 것이다. (단 출력 같은 경우 증가하는 순서대로 출력하시오)

만약 N = 3일경우를 생각해 보자

자리에는 0 또는 1이 올 수 있다. 이것을 그래프로 그려보자. 첫 번째 자리에 0 이오고 두 번째 자리에 0이 오고 3번째 자리에 0이 오는 000인 경우가 있을 것이고 그다음에 3번째 자리가 1이 되는 경우인 001 … 이런 식으로 재귀적으로 반복하게 됩니다.

p.s 사실 위에서부터 아래로 내려가는 것을 depth라고 하고 아래에서 위를 height라고 하고, depth는 0부터 시작하지만, 편의상 높이라고 칭할게요.

1 그래프

위 그래프에서 d(4)을 도착할 때마다 출력하면 된다(왼쪽부터 오른쪽 순서대로)

2 -1 ) 가지는 2개이므로 재귀함수 내에 본인을 2번 호출한다.

2 - 2) 높이가 4가 될 때까지 그래프 탐색을 진행한다.

코드

package baekjoon.tree;
import java.util.*;
import java.io.*;

public class backtracking1 {

    public static int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();

    public static void dfs(int h) {
        if (h == n + 1) {
            print();
            return;
        }

        arrayList.add(0);
        dfs(h + 1);
        arrayList.remove(arrayList.size() - 1);

        arrayList.add(1);
        dfs(h + 1);
        arrayList.remove(arrayList.size() - 1);

    }

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args)throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        dfs(1);
    }
}

위 코드보다 좀 더 나은 코드

package baekjoon.tree;
import java.util.*;
import java.io.*;

public class backtracking1 {

    public static int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();

    public static void dfs(int h) {
        if (h == n + 1) {
            print();
            return;
        }

        for(int i = 0; i < 2; i++) {
            arrayList.add(i);
            dfs(h + 1);
            arrayList.remove(arrayList.size() - 1);
        }
    }

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args)throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        dfs(1);
    }
}

파이썬으로 하시는 분들은 아래 라이브러리가 있는데 알아두면 좋아요.

과제할 때는 사용 안 하고 과제하고 나서 아래 라이브러리를 사용하면서 과제를 풀어보고 이렇게 2번씩 하시면 좋을 거 같아요. → 갓 파이썬 (몇몇 코테에서 아래 라이브러리 사용 못하게끔 하는 곳도 있어요! )

from itertools import permutations # 순열
from itertools import product # 중복 순열
from itertools import combinations # 조합
from itertools import combinations_with_replacement # 중복 조합

연습문제 1

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

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

연습문제 2

15649번: N과 M (1)

www.acmicpc.net

연습문제 3

15650번: N과 M (2)

www.acmicpc.net

문제 1번 코드

💡 문제 1번 풀이 문제를 쉽게 요약하자면, n𝜋r의 모든 경우의 수를 출력하는 문제이다. 즉 중복순열을 구하는 문제이기 때문에 위에 경우와 같이 조건 없이 출력하면 된다. 재귀함수 내 for문을 통해 문제를 해결할 수 있다.

3번 문제 같은 경우 자바로 할 때, StringBuilder를 사용하지 않으면 시간초과 가 발생합니다. → Sytem.out.printl()은 특히 문자를 합치는 게 많을 경우 엄청 느려요.

package baekjoon.b15651;

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

public class B15651 {

    public static int n, m;
    public static ArrayList<Integer> arrayList = new ArrayList<>();
    public static StringBuilder sb = new StringBuilder();

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            sb.append(arrayList.get(i)).append(" ");
        }
        sb.append("\\n");
    }
    public static void dfs(int h) {
        if(h == m + 1) {
            print();
            return;
        }
        for(int i = 1; i <= n; i++) {
            arrayList.add(i);
            dfs(h + 1);
            arrayList.remove(arrayList.size() - 1);
        }

    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dfs(1);

        System.out.println(sb);

    }
}

문제 2번 코드

💡 문제 1번 풀이 문제를 쉽게 요약하자면 nPr의 모든 경우의 수를 출력하는 문제이다. 즉 중복순열이 아니기 때문에 일반적인 순열을 계산하는 문제이다. 따라서 하나의 수열에 같은 숫자가 존재하면 안 된다. 이러한 경우를 visited라는 boolean 배열을 통해서 사용했는지 안 했는지 체크를 한다면 쉽게 해결할 수 있다.

package baekjoon.b15649;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B15649 {

    public static int n, m;
    public static ArrayList<Integer> arrayList = new ArrayList<>();
    public static boolean[] visited;

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
    }
    public static void dfs(int h) {
        if(h == m + 1) {
            print();
            return;
        }
        for(int i = 1; i <= n; i++) {
            if(visited[i]) continue;

            arrayList.add(i);
            visited[i] = true;
            dfs(h + 1);
            arrayList.remove(arrayList.size() - 1);
            visited[i] = false;
        }

    }
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        visited = new boolean[n + 1];

        dfs(1);
    }
}

문제 3번 코드

💡 문제 3번 풀이 문제를 쉽게 요약하자면 nCr의 모든 경우의 수를 출력하는 문제이다. 2개를 뽑는다고 했을 때 (1,2) = (2,1)과 같기 때문에 (1,2)를 뽑았으면 (2,1)은 뽑으면 안 된다. 이러한 적용을 매개변수를 통해 해결할 수 있다. 높이 h와 노드 값(Value)인 v를 같이 매개변수로 넘긴다. 이후 재귀함수 내에서 반복문을 돌 때 v보다 큰 값을 돌면 순서 상관없이 중복 안되게 뽑게끔 진행할 수 있다.

package baekjoon.b15650;

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

public class B15650 {

    public static int n, m;

    public static ArrayList<Integer> arrayList = new ArrayList<>();

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
    }

    public static void dfs(int v, int h) {
        if(h == m + 1) {
            print();
            return;
        }
        for(int i = v; i <= n; i++) {
            arrayList.add(i);
            dfs(i + 1, h + 1);
            arrayList.remove(arrayList.size() - 1);

        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dfs(1,1);
    }
}

728x90

'Algorithm > 알고리즘 강의 자료' 카테고리의 다른 글

재귀함수 분석 & 초 간단 트리 이론 (0)	2024.04.22
스택의 활용(연산 표기법 : 중위 표기법, 전위 표기법, 후위 표기법) + 큐 연습문제 (0)	2024.04.22
알고리즘 시간 복잡도 (0)	2024.04.22
dx dy technique & inRange (0)	2024.04.08

공돌이 프로그래밍

백트래킹이란

'Algorithm > 알고리즘 강의 자료' 카테고리의 다른 글

티스토리툴바

백트래킹이란

'Algorithm > 알고리즘 강의 자료' 카테고리의 다른 글

관련글

티스토리툴바