글 읽기 - DFS에서 백트래킹에 관해

instarbucks 6년 전 0

안녕하세요!

DFS 문제를 풀다가 헷갈리는? 부분이 생겨서 글을 올립니다.

이 코드에서 64~73번째 부분을 보면

DFS를 빠져나오면서 depth를 줄인 후, for문을 다 돌고나면

visited[x][y]=0; 해주는 부분이 있습니다.

이 부분이 이해가 잘(?) 안갑니다.

왜 depth를 줄여야 하는지
x,y 정점을 기준으로 4방향을 모두 검사했는데 왜 x, y정점만 0으로 바꿔주는지

이 부분에서 이해가 잘안되다보니까

다른 dfs 문제를 풀 때도, 항상 여기서 막히더라구요.

제 질문이 난해하죠....선배님들의 조언 부탁드려요!

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

public class Main {
	static int N,M;
	static int[][] arr;
	static int[][] visited;
	
	static int sum=0;
	static int MAX=0;
	static int depth=0;
	
	
	static int[] dx ={-1,0,1,0};
	static int[] dy ={0,-1,0,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());
		
		arr = new int[N][M];
		visited = new int[N][M];
		
		for(int i=0; i<N; i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++){
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				DFS(i,j);
				sum=0;
				depth=0;
				Exception(i,j);
				sum=0;
			}
		}
		
		System.out.println(MAX);
	
    }//main
     
	public static void DFS(int x, int y){
		//종료 조건 : 4방향 다 체크해봤을 때, max<sum
		if(depth==4){
			if(MAX<sum) MAX=sum;
			return;
		}
		
		visited[x][y]=1;
		sum+=arr[x][y];
		
		for(int i=0; i<4; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>=0 && nx<N && ny>=0 && ny<M && visited[nx][ny]==0){
				depth++;
				DFS(nx,ny);
				depth--; 
			}//if
			
		}//for
		
		visited[x][y]=0;
		sum-=arr[x][y];

		
	}//DFS
	
	public static void Exception(int i, int j){
/**생략했습니다*/
			
	}

}

chogahui05 6년 전 0

백 트래킹이라는 게 모든 가짓수를 다 탐색해 보는 것이잖아요.

이 문제를 예로 들어봅시다. - - - - 이런 식으로 있는 블럭을 예로 들어보고요.

1번째 블록을 놓았을 때 위치를 (x,y)라고 해 봅시다.

그러면 2번째 블록을 놓아봐야 하잖아요. 이 때 재귀 함수가 한 번 호출이 됩니다.

그런 탐색 과정이 다 끝나면 return이 될 거고요. depth가 1인 상태에서 계산을 하겠지요.

그리고 나서 visit[x][y] = 0을 하는 이유는

1번째 블록을 (x,y)에 놓는 경우도 있지만 다른 위치에 놓는 경우도 있기 때문에, 그 부분도 탐색을 해 주기 위함입니다.

chogahui05 6년 전 0

그리고, depth 같은 경우, 전역 변수로 선언되어서 호출을 할 때 증가시키고, 호출이 끝날 때 감소시키는 건데.

이 부분 역시 마찬가집니다. 블럭을 하나 빼면, 블럭이 하나 감소하기 때문에 그런 거고요.

저 같으면

DFS(int x,int y,int depth)

이렇게 선언할 거 같습니다. 어짜피 depth라는 걸 하나 더 선언해도 이해하기는 어렵지 않거든요.

그러면 깊이 하나 증가시킨다면

DFS(x,y,depth+1)

이렇게 해 버리면 되겠죠.

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

문제

문제

출처

ICPC

DFS에서 백트래킹에 관해

instarbucks 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말