[Python] BOJ / 3109번 / 빵집

3109번: 빵집

---

📝 풀이

• 그래프 탐색을 통해 가스관과 빵집을 연결하는 파이프라인의 최댓값을 구하는 문제
• 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 함.
• 각 칸은 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선으로 연결할 수 있음
  • (-1, 1), (0, 1), (1, 1)
• 연결하는 파이프라인은 서로 겹칠 수 없음
  • visited 배열을 통해 구현
• x축이 (c - 1)열에 도착했다는 것은 파이프라인이 성공적으로 연결되었다는 뜻

---

💻 소스 코드

import sys

input = sys.stdin.readline
dy = (-1, 0, 1)

def dfs(y, x):
    if x == c - 1:
        return True
    
    for i in range(3):
        ny = y + dy[i]
        nx = x + 1

        if not 0 <= ny < r or nx >= c or graph[ny][nx] == 'x':
            continue
        if not visited[ny][nx]:
            visited[ny][nx] = True
            if dfs(ny, nx):
                return True

    return False

r, c = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]
ans = 0

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

print(ans)