[BJ3109] 빵집

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

[BJ3109] 빵집

yeomss 2022. 9. 9. 14:04

백준 - 빵집

문제 링크

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

3109번: 빵집

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던

www.acmicpc.net

문제 입출력

5 5
.xx..
..x..
.....
...x.
...x.

문제 풀이

//package problem.BJ;


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int ans, R, C;
	static char[][] map;

	// 우선순위가 존재
	// 오른쪽위, 오른쪽, 오른쪽아래
	static int[] dy = { -1, 0, 1 };
	static int[] dx = { 1, 1, 1 };

	static Queue<int[]> q = new ArrayDeque<>();


	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		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];
		for (int i = 0; i < R; i++) map[i] = br.readLine().toCharArray();

		// 탐색 dfs
		for (int i = 0; i < R; i++) if (dfs(i, 0)) ans++;

		// 탐색 bfs -> 틀렸다고 나옴
		// for (int i = 0; i < R; i++) if (bfs(i, 0)) ans++;

		System.out.println(ans);

	} // end main


	private static boolean dfs(int y, int x) {
		map[y][x] = 'x';

		if (x == C - 1) return true;

		for (int d = 0; d < 3; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if (map[ny][nx] == 'x') continue;

			// for (int i = 0; i < R; i++) System.out.println(Arrays.toString(map[i]));
			// System.out.println();

			if (dfs(ny, nx)) return true;
		}

		return false;

	} // end dfs


	private static boolean bfs(int sy, int sx) {
		q.offer(new int[] { sy, sx });
		map[sy][sx] = 'x';

		while (!q.isEmpty()) {
			int[] yx = q.poll();
			int y = yx[0];
			int x = yx[1];

			map[y][x] = 'x';

			if (x == C - 1) return true;

			for (int d = 0; d < 3; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];

				if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
				if (map[ny][nx] == 'x') continue;

				q.offer(new int[] { ny, nx });
				break;
			}

		}

		return false;

	} // end bfs
}