[백준] 3109 빵집

✔️ 문제 링크

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

💡 핵심 아이디어

1️⃣ dfs로 그래프를 순회

2️⃣ 탐욕적으로 출발점은 위에서 아래로 고려하고 이동 방향은 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 고려하여 서로 경로가 겹치지 않게, 이미 한번 순회를 했던 곳은 다시 순회를 하지 않도록 설정해준다.

⭐️ 소스 코드

r_dir = [-1, 0, 1]
c_dir = [1, 1, 1]


def dfs(r, c):
    maps[r][c] = 'x'
    if c == C - 1:
        return True

    for dr, dc in zip(r_dir, c_dir):
        nr = r + dr
        nc = c + dc

        if 0 <= nr < R and 0 <= nc < C and maps[nr][nc] == ".":
            if dfs(nr, nc):
                return True
    return False


if __name__ == '__main__':
    R, C = list(map(int, input().split()))
    maps = []

    for _ in range(R):
        arr = list(input())
        maps.append(arr)

    ans = 0
    for v in range(R):
        if dfs(v, 0):
            ans += 1
    print(ans)