빵집
백준 3109: 빵집
풀이
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);
}
}
}
}