빵집


백준 3109: 빵집

문제보기
Alt text

풀이

DFS 이용
원웅이의 빵집(맨 오른쪽 열)에 도착하면 탐색을 중단하고 가스관 개수+1
-> 남은 for문을 돌지 않는다는 뜻(break)

소스코드

import java.util.Scanner;

public class Main {
	static class Node{
		int r, c;
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	static int[] dr = {-1,0,1};
	static int[] dc = {1,1,1};
	static int R;
	static int C;
	static int[][] map;
	static boolean[][] visited;
	static int cnt=0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		map = new int[R][C];
		visited = new boolean[R][C];
		for(int i=0; i<R; i++) {
			String str = sc.next();
			for(int j=0; j<C; j++) {
				Character ch =str.charAt(j);
				if(ch=='.')
					map[i][j]=0;
				else if(ch=='x')
					map[i][j]=-1;
			}
		}
		
		for(int i=0; i<R; i++) {
			flag = false;
			dfs(i,0);
		}
		
		System.out.println(cnt);
	}
	
	public static boolean flag;
	
	public static void dfs(int r, int c) {
		map[r][c] = 1;
		if(c==C-1) {
			cnt++;
			flag = true;
			return;
		}
		
		for(int d=0; d<3; d++) {
			if(flag) break;
			int nr = r+dr[d];
			int nc = c+dc[d];
			if(nr>=0 && nc>=0 && nr<R && nc<C && map[nr][nc]==0) {
				dfs(nr, nc);
			}
		}
	}
}