[Python/파이썬] - 백준(BOJ) 3109번 : 빵집

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

3109번: 빵집

 

남의 가스를 훔친다는 비양심적인 그리디 문제

DFS로 우선 탐색할 지점만 잘 생각한다면 쉬운 문제이다.

 

맨 위에서 시작할 경우 건물을 피해 위쪽을 먼저 탐색하고 반대의 경우에는 아래쪽을 먼저 탐색하면 된다.

처음에는 가스관에 도달하면 경로를 저장했는데 그렇게 하니 시간초과가 됐다.

어떻게 시간을 줄일까 생각해보니 어차피 어떠한 지점에 간 후 가스관에 도달하지 못하면 그 경로는 안가도 되니

이동할 때마다 경로를 저장하니 맞았습니다! 가 나왔다.

 

import sys
input = sys.stdin.readline

def dfs(y, x):
    global answer
    arr[y][x] = 'x'
    if x == m-1:
        answer += 1
        return 1

    if 0 <= y-1 and arr[y-1][x+1] != 'x':
        if dfs(y-1, x+1):
            return 1
    if arr[y][x+1] != 'x':
        if dfs(y, x+1):
            return 1
    if y+1 < n and arr[y+1][x+1] != 'x':
        if dfs(y+1, x+1):
            return 1
    return 0

n, m = map(int,input().split())
arr = [list(str(input().strip())) for _ in range(n)]
answer = 0
for i in range(n):
    dfs(i, 0)
print(answer)