글 읽기 - 백트래킹 이해가 전혀 안됩니다 ㅠㅠ

le_effort 4년 전 0

다른 블로그의 성공코드인데요

22번째 줄이 이해가 안됩니다

왜 저게 있는 건가요...?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	static int[] arr;
	static boolean[] visit;
	static StringBuilder sb = new StringBuilder();
	
	private static void dfs(int n, int m, int d) {
		if(d == m) {
			for(int a : arr) sb.append(a + " ");
			sb.append("\n");
			return;
		}
		
		for(int i = 1; i <= n; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[d] = i;
				dfs(n, m, d+1);
				visit[i] = false;
			}
		}
		return;
	}
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
		arr = new int[m]; visit = new boolean[n+1];
		
		dfs(n, m, 0);
		System.out.print(sb);
	}
}

kerochuu 4년 전 5

백트래킹은 dfs와 코드가 거의 비슷한데, 말씀하신 22번째 줄의 유무로 백트래킹인지 dfs인지 나뉘게 됩니다.

22번째 줄의 경우, 재귀를 들어가기 전에 처리한 visit[i] = true를

재귀에서 나온 뒤 false로 바꿔주는 작업을 통해

"들어가기 전 했던 행동을 들어가기 전의 상태로 돌려놓게" 되며

이는 백트래킹의 가장 중요한 개념이라고 생각합니다.

결국 위와 같은 작업을 통해 해당하는 i점을 나중에 다시 재탐색 할 수 있게 됩니다.

12번째 줄에 디버깅 코드를 잘 넣으신 것 같은데

22번째줄 코드의 유무에 따른 값을 한번 잘 생각해보시면 이해에 큰 도움이 될 것 같습니다.

도움이 되셨으면 좋겠네요.

yhc3006 4년 전 1

22번 코드를 작성하지 않으면 한번씩만 방문합니다.

백트래킹의 정의를 다시 한번 보시는게 나을거같아요.

기저사례에 해당되면 return이 되고 말그대로 왔던 길을 되돌아가는 겁니다.

되돌아갈때 왔던길의 방문체크를 해제시켜줘야 합니다.

le_effort 4년 전 0

감사합니다

혹시 디버깅코드라는게 무슨 의미로 말씀하신건지 궁금합니다 ㅠ

kerochuu 4년 전 2

아아 단순히 해당 dfs()함수의 종료조건에 다다를 시 sb.append하는 구문을 디버깅코드라고 말한거였습니다.

간단히 문제에 대해 좀 더 설명하자면

백트래킹은 재귀를 타고 들어가기 직전에 했던 작업을

재귀에서 빠져 나왔을때 그대로 돌리는 작업을 통해서

해당 점을 재방문 할 수 있도록 해야합니다.

visit[i] = false를 하지 않으면 두번다시 해당 점은 재방문이 불가능하기 떄문에 false로 바꿔주는 작업이 필요합니다.

정말 중요한 내용이고 여러 코테에서도 자주 나오는 알고리즘이니 꼭 숙지해두시면 좋을 것 같네요

le_effort 4년 전 0

답변 정말 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

백트래킹 이해가 전혀 안됩니다 ㅠㅠ

le_effort 4년 전 0

kerochuu 4년 전 5

yhc3006 4년 전 1

le_effort 4년 전 0

kerochuu 4년 전 2

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말