[백준] 3109번 - 빵집 (파이썬)

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

# 빵집
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(input().strip()))

dx = [-1, 0, 1]
dy = [1, 1, 1]


def pipe(x, y):
    global result
    arr[x][y] = 'o'
    if y == M-1:
        result += 1
        return True
    for k in range(3):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < N and 0 <= ny < M:
            if arr[nx][ny] != 'x' and arr[nx][ny] != 'o':
                if pipe(nx, ny):
                    return True


result = 0
for i in range(N):
    pipe(i, 0)
print(result)

 

그리디, DFS

1. 입력을 받고 pipe함수(dfs) 실행

    - 매 파이프마다 가장 위쪽에 붙는 것을 우선순위로(그리디)

    - 마지막 열에 도착하면 모든 함수 종료

    - (시간초과 예방) 단, 가장 위에서 파이프를 설치를 했으나 마지막 열에 도달 하지 못한 곳은

       추후 파이프를 설치를 해도 도달하지 못하므로 설치한 파이프('o')를 원상복귀('.')하지 않아도 된다.

2. result 출력