자바 | 백준 | 3109 | 빵집

 

Solution

1. 오른쪽 위, 오른쪽, 오른쪽 아래 순서로 dfs 진행한다.

// 3109, 빵집
package BOJ;

import java.io.*;
import java.util.*;

public class BOJ_3109 {

	static int R, C;
	static char[][] board;
	static int[] dx = { -1, 0, 1 };
	static int[] dy = { 1, 1, 1 };
	static boolean flag;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		board = new char[R][C];
		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				board[i][j] = s.charAt(j);
			}
		}


		int cnt = 0;
		for (int i = 0; i < R; i++) {
			flag = false; // 파이프 설치 불가능하다고 초기화
			dfs(i, 0);

			if (flag)
				cnt++;
		}
		System.out.println(cnt);
	}

	static void dfs(int r, int c) {
		// 이미 파이프 만들어졌으면
		if (flag) return;

		board[r][c] = 'o';
		
		// 빵집에 도달 했으면 true
		if (c == C - 1) {
			flag = true;
			//System.out.println("flag: true");
			return;
		}
		
		for (int i = 0; i < 3; i++) {
			int nx = r + dx[i];
			int ny = c + dy[i];

			// 범위 밖이면
			if (0 > nx || nx >= R || 0 > ny || ny >= C)
				continue;

			// 이미 파이프 설치 됐거나 벽이면
			if (board[nx][ny] == 'o' || board[nx][ny] == 'x')
				continue;

			if (board[nx][ny] == '.') {
				dfs(nx, ny);
			}

		}

	}

}

 

www.acmicpc.net/problem/3109

3109번: 빵집