[백준] 3109번 빵집 (JAVA, 백트래킹)

www.acmicpc.net/problem/3109

3109번: 빵집

중간에 아니면 다른 경우를 탐색한다. 혹은 그만둔다. (백트래킹)

파이프를 가장 많이 연결하려면 최대한 위쪽으로 연결한다.

연결이 하나라도 되면 다른 경우는 생각하지 않고 다음 열에서 파이프라인을 연결을 시작한다.

 

import java.util.Scanner;

public class Main {
	static int r,c;
	static int map[][];
	static boolean vis[][];
	static int xpos[]= {1,1,1};
	static int ypos[]= {-1,0,1}; //대각선 위, 오른쪽, 대각선 아래 
	static int ans;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		map=new int[r][c];
		vis=new boolean[r][c];
		for (int i = 0; i < r; i++) {
			String s=sc.next();
			for (int j = 0; j < c; j++) {
				map[i][j]=s.charAt(j);
			}
		}
		for (int i = 0; i < r; i++) {
			vis[i][0]=true; //안해줘도 됨. 
			ans+=check(i,0);
		}
		System.out.println(ans);
	}


	
	private static int check(int y,int x) {
				if(x==c-1) { //끝에 도달하면 해당 열의 파이프라인은 가능
					return 1; //1리턴
				}
				for (int k = 0; k < 3; k++) {
					int yy=y+ypos[k];
					int xx=x+xpos[k];
					if(xx>=c || yy>=r || yy<0)continue;
					if(vis[yy][xx]==true)continue;
					if(map[yy][xx]=='.') {
						vis[yy][xx]=true;
						if(check(yy,xx)==1)return 1; //한번 도달하면 다른 경우는 생각x
					}
				}
				return 0;
			
	}
	
}