[백준 3109] 빵집

문제 링크

사용 언어: Java

1. 구상

• 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색

• 마지막 열에 도착하면 종료

• 현재 위치가 가능한지 확인하고 가능하다면 각 방향이 가능한지 재귀호출
  → 오른쪽 위의 경우, 행 번호가 0보다 커야 가능하다.
  → 오른쪽 아래의 겨우, 오른쪽 아래로 갔을 때의 행 번호가 R보다 작아야 한다.

코드 및 알고리즘 참고 링크

2. 구현

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

public  class Main {	
	
	//파이프 지도
	static char[][] map;
	//R = 세로, C = 가로
	static int R, C;
	//파이프라인의 최대 개수
	static int cas;
	
	public static void main(String[] args) throws NoSuchElementException, IOException {
		Scanner s = new Scanner(System.in);		
		
		R = s.nextInt();
		C = s.nextInt();
		
		map = new char[R][C];
		
		//입력 받기
		for (int i = 0; i < R; i++)
			map[i] = s.next().toCharArray();
		
		//최대 파이프라인 찾기
		for (int i = 0; i < R; i++) {
			//파이프라인이 가능하다면 경우의 수에 추가
			if (sol(i, 0))
				cas++;
		}
		
		System.out.println(cas);
		
	}
	
	//dfs를 이용하여 가능한 파이프라인 찾기
	static boolean sol (int x, int y) {
		//해당 자리에 건물이 있다면 false 반환
		if (map[x][y] == 'x')
			return false;
		//그렇지 않다면 파이프 놓기
		else
			map[x][y] = '-';
		
		//마지막 열에 도착하면 끝내기
		if (y == C - 1)
			return true;
		
		//오른쪽 위 방향 탐색
		if (x > 0 && map[x-1][y+1] == '.') {
			if (sol(x-1, y+1))
				return true;
		}
		
		//오른쪽 방향 탐색
		if (map[x][y+1] == '.') {
			if (sol(x, y+1))
				return true;
		}
		
		//오른쪽 아래 방향 탐색
		if (x + 1 < R && map[x+1][y+1] == '.') {
			if (sol(x+1, y+1))
				return true;
		}		
		
		return false;
	}
	

}