[백준 - Python] 3109 - 빵집

0.  문제 링크

 

 

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

3109번: 빵집

---

1.  풀이 방법

 

 

1. 방향의 우선순위는 무조건 오른쪽 위, 오른쪽, 오른쪽 아래로 해야 한다.
2. 그리고 왼쪽 상단부터 왼쪽 하단으로 차례로 돌면서 길을 찾는다.
3. 나는 따로 방문 표시 복구를 하지 않았는데, 어차피 위에서 가지 못한 길이라면, 아래에서도 가지 못하는 길이기 때문에 복구하지 않았다.
4. 따라서 dfs로 문제를 풀었다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline


def dfs(y, x):
    maps[y][x] = 'x'        ## 방문 처리, 어차피 위에 행에서 못가면 아래 행도 못감. 복원할 필요 없음

    if x == c - 2:
        return True

    if y > 0 and maps[y - 1][x + 1] != 'x':
        ## == '.' 보다 != 'x'가 300ms 가량 더 빠름
        if dfs(y - 1, x + 1):
            return True

    if maps[y][x + 1] != 'x':
        if dfs(y, x + 1):
            return True

    if y < r - 1 and maps[y + 1][x + 1] != 'x':
        if dfs(y + 1, x + 1):
            return True
    
    return False


if __name__ == "__main__":
    r, c = map(int, input().split())
    maps = [list(input().strip()) for _ in range(r)]

    ans = 0
    for i in range(r):
        if dfs(i, 0):
            ans += 1

    print(ans)

 

---

3.  마무리