백준 3109 <빵집>

이 문제는 DFS 문제임과 동시에 어떻게 하면 갔던 곳을 방문하지 않게 할까? 가 주요한 문제이다.

 

이 문제를 해결하기위해서는 두 가지 신경 써줘야 하는 부분이 있었다.

1. 길을 연결 하고 나서 돌아갈 때 처리 방법
2. 길을 연결 하지 못했다면 돌아갈 때 처리 방법

첫 번째 방법은 return 값을 boolean형으로 선언해서 true로 리턴하게 하면 된다.

다른 방법은 flag를 한 개 선언해서 이용해주면 된다.

이렇게 처리해 주지 않으면 

 

이렇게 다음 빈 공간으로 이동하기 때문에 원래 값은 1이 되어야 하는데 2가 출력되게 됩니다.

 

두 번째 방법은 이미 방문했던 곳을 다시 방문할 수 없게 방문처리를 계속하는 것입니다.

그렇지 않으면 이전에 방문했지만 방문 표시를 제거해줬기 때문에 그 지점을 다시 방문하게 되어 시간 초과가 발생합니다.

 

이렇게 방문한 곳을 다시 방문하지 않게 해주는 부분이 가지치기라고 하여 백트래킹이라는 기술을 사용하게 됩니다.

 

이렇게 모든 행 첫 번째 열을 검사하면서 저는 flag라는 boolean형 변수를 두어 처리를 했습니다.

DFS로 앞으로 나아가면서 위쪽 직선 아래쪽을 검사하면서 갈 수 있으면 진행하도록 해서 구현을 하도록 했습니다.

 

이문제에서 중점은 방문한 곳을 다시 방문 못하게 해서 시간을 줄이는 것입니다.

 

전체 코드

import java.util.*;

public class Main{

	
	static String map[];
	static int R,C,result,visit[][],dir[][]= {{-1,1},{0,1},{1,1}};
	static boolean flag;
			
   public static void main(String[] args) {
      Scanner kb = new Scanner(System.in);
      R=kb.nextInt();
      C=kb.nextInt();
      visit=new int[R][C];
      map=new String[R];
      for(int i=0;i<R;i++) {
    	  map[i]=kb.next();
      }
      for(int i=0;i<R;i++) {
    	  flag=true;
    	  dfs(i,0);
      }
      System.out.println(result);
      
   }
   public static void dfs(int h,int w) {
	   if(w==C-1) {
		   flag=false;
		   result++;
		   return;
	   }
	   for(int i=0;i<3;i++) {
		   int x=h+dir[i][0];
		   int y=w+dir[i][1];
		   if(x>=0&&x<R&&map[x].charAt(y)!='x'&&visit[x][y]==0) {
			   visit[x][y]=1;
			   dfs(x,y);
			   if(flag==false) {
				   return;
			   }
		   }
	   }
   }

   
}