BOJ - 3109 - 빵집

import sys

dx = [-1, 0, 1]

def DFS(x, y, R, C, table, visit):
    if y == C-1: return True

    for k in range(len(dx)):
        nx = x + dx[k]
        if 0 <= nx < R and table[nx][y+1] == '.':
            if visit[nx][y+1] is False:
                visit[nx][y+1] = True
                if DFS(nx, y+1, R, C, table, visit):
                    return True
    return False

def solution():
    R, C = map(int, sys.stdin.readline().split())
    table = []
    for _ in range(R):
        table.append(list(sys.stdin.readline().strip()))
    visit = [[False] * C for _ in range(R)]

    ret = 0
    for i in range(R):

        if table[i][0] == '.':
            if DFS(i, 0, R, C, table, visit):
                ret += 1
    print(ret)

solution()

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