[백준 3109]빵집

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

1)문제분류

-DFS

-백트레킹

-그리디

2)문제해결

-각 (0~R,0)에서 dfs를 돌면서, 마지막 열 (0,C-1)만날때 +1을 한다.

- dfs에서 빵집을 연결하든 안하든,탐색한 chk[][]를 false로 안바꾸는 이유는

- 어차피 그 다음 탐색 시에 그 chk[][] 지점으로 가도 결과는 같기때문에 또 다시 두번 갈 필요가 없다! 

  

//12시 50분 ~1시 20분

#include<iostream>

using namespace std;

char map[10002][502];

bool chk[10002][502];

int R, C;

int xrr[3] = { -1,0,1 };

int yrr[3] = { 1,1,1 };

int dfs(int x,int y)

{

if (y == C - 1)return 1;

for (int i = 0; i < 3; i++)

{

int curx = x + xrr[i];

int cury = y + yrr[i];

if (curx >= 0 && curx < R && cury >= 0 && cury <C&& chk[curx][cury] == 0 && map[curx][cury] == '.')

{

chk[curx][cury] = 1;

if (dfs(curx, cury))

{

return 1;

}

}

}

return 0;

}

int main()

{

scanf("%d %d", &R, &C);

for (int i = 0; i < R; i++)

{

for (int j = 0; j < C; j++)

{

cin >> map[i][j];

}

}

int ans = 0;

for (int i = 0; i < R; i++)

{

ans+=dfs(i,0);

}

cout << ans << endl;

}