[백준] 3109번:빵집 (Java 자바)

문제

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

3109번: 빵집

 

풀이 및 소스코드

 

오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래로 이동하므로

x는 {-1, 0, 1} y는 +1 씩 더해주면 된다.

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

public class Main {
	static int[] dx = { -1, 0, 1 };
	static int r, c, res;
	static char[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		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();
		}

		for (int i = 0; i < r; i++) { //행별로 연결할 수 있는 파이프라인을 찾는다.
			connect_pipe(i, 0);
		}
		System.out.println(res);
	}

	public static boolean connect_pipe(int x, int y) {
		if (y == c - 1) { //빵집을 만나면 true 리턴
			res++;
			return true;
		}
		for (int i = 0; i < 3; i++) {
			int nowx = x + dx[i];
			int nowy = y + 1;
			if (!((0 <= nowx && nowx < r) && (0 <= nowy && nowy < c))) //맵을 벗어나면 다음 반복으로 넘어감
				continue;
			if (map[nowx][nowy] == '.') {
				map[nowx][nowy] = 'x'; //방문 표시
				if (connect_pipe(nowx, nowy)) //다음 파이프라인 연결 가능한 곳 찾기
					return true; //if문이 실행되었다는 것은 연결이 가능하다는 것이므로 true 리턴
			} 
		}
		return false; //어떠한 조건에도 걸리지 않았다는 건 연결할 수 없다는 것이므로 false 리턴
	}

}