BOJ - 3109 ) 빵집

 

---

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

3109번: 빵집

---

벽을 피해 파이프를 연결하는 문제이다. 파이프는 현재좌표에서 

x 좌표는 +1 / y 좌표는 -1,0,1인 지점에 벽이 아닌공간에 설치할 수 있다.

물론 중복되게 설치할 수없다.

 

따라서 DFS탐색 중 연결이 되었다면, 적절하게 끊어서 더이상 전진하지 못하게 해야한다.

전역변수를 설정하여 처음 DFS실행 좌표를 저장해두고 파이프연결이 완성되면 끊는 식으로 구현하였다.

 

 

---

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

public class 빵집 {
	public static char map[][];
	public static boolean visit[][];
	public static int r,c,answer;
	public static boolean end[];
	public static int start;
	public static int dir[][] = {{-1,1},{0,1},{1,1}};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new char[r][c];
		visit = new boolean[r][c];
		end = new boolean[r];
		for(int i = 0 ; i < r ; i++) {map[i] = br.readLine().toCharArray();}
		for(int i = 0 ; i < r ; i++ ){
			start = i;
			dfs(i,0);
		}
		System.out.println(answer);
	}
	
	public static void dfs(int i, int j) {
		visit[i][j] = true; 
		for(int k = 0 ; k < 3 ; k++) {
			int ni = i + dir[k][0]; // y좌표
			int nj = j + dir[k][1]; // x좌표 항상 1
			if( ni>=0 && nj >=0 && ni < r && nj <c ){
				if(map[ni][nj] =='.' && !visit[ni][nj]) {
					if(nj == c-1) {
						answer++;
						end[start] = true; // 출발번째를 계속할껀지?
						return;
					}
					dfs(ni,nj);
					if(end[start]) return;
				}
			}
		}
	}
}

---