[BAEKJOON_3109 - JAVA] 빵집

문제

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

3109번: 빵집

 

 

과정

 

1. DFS를 활용.
2. 우상, 우, 우하 순서대로 3방 탐색을 진행.
3. 파이프가 연결된 경우(끝열에 도착) static에 위치한 boolean type의 root 변수를 true로 변경.
4. if문을 타고 root를 활용해 재귀 탈출.
5. root = flase 초기화.
6. 출발가능한 행만큼 반복후 출력.

 

풀이

 

• 별도의 방문관리 없이 해당 값을 변경해주었다.
  만약 해당 자리를 지나는 파이프가 연결되지 않더라도 그 길을 지나는 파이프는 모두 연결이 불가능하기 때문이다.
  (참고 : 파이프는 우상,우,우하로만 설치가 가능하다고 문제에 제시됐다.)
  (이해가 되지 않는다면, 예제를직접 그려보는 편이 확실함.)
• 이 문제를 BFS로 풀었다면 성공한 했을 경우 되돌아가거나 지금까지 온길을 다시 마킹해야 한다고 생각해 DFS로 접근했고 static 위치에 boolean변수를 통해 성공한경우 탐색을 끝내고 재귀를 종료하는 방식을 사용했다.

 

 

알고리즘 지식

• 그리디 알고리즘
• 백트래킹

 

 

JAVA코드

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

public class BJ3109_빵집 {

	static int R, C, cnt; // 행,렬
	static boolean root;
	static char map[][]; // 입력받는 map
	static int dy[] = { -1, 0, 1 }; // 우상, 우, 우하
	static int dx[] = { 1, 1, 1 };

	// 범위 체크
	public static boolean isValid(int row, int col) {
		if (row < 0 || row >= R || col < 0 || col >= C) {
			return false;
		}
		return true;
	}

	private static void dfs(int row, int col) {

		if (col == C - 1) {
			root = true;
			cnt++;
			return;

		}

		// 3방 탐색
		for (int k = 0; k < 3; k++) {
			int nextRow = row + dy[k];
			int nextCol = col + dx[k];

			// 범위 && 파이프 자리 검사
			if (isValid(nextRow, nextCol) && map[nextRow][nextCol] == '.') {
				map[row][col] = 'x';
				dfs(nextRow, nextCol);
				if (root) {
					return;
				}
			}
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		// input
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
		}
		// end of input;

		for (int i = 0; i < R; i++) {
			root = false;
			dfs(i, 0);
		}

		// output
		sb.append(cnt);
		bw.write(sb + " ");
		bw.flush();
		bw.close();
		br.close();

	} // end of main

}