[골드 2] 백준 3109 - 빵집 (파이썬)

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

풀이

가스관이 있는 빵집의 왼쪽 열에서 시작해 오른쪽 열까지 파이프를 설치할 수 있는 최대 개수를 구하는 것이다.

• '.'은 빈 칸, 'x'는 설치 불가능한 건물
• 파이프는 오른쪽 위 / 오른쪽 / 오른쪽 아래로만 이동 가능
• 파이프는 겹치면 안 됨
• 출발은 각 행의 첫 번째 열 (즉, (i, 0))

def dfs(r, c):
    visit[r][c] = True
    if c == C - 1:  # 오른쪽 끝 도착
        return True

DFS는 3방향 우선순위로 탐색을 진행한다.

1. 오른쪽 위 (r - 1, c + 1)
2. 오른쪽 (r, c + 1)
3. 오른쪽 아래 (r + 1, c + 1)

방문한 적 없고 빈 칸이면 DFS 재귀 호출, 도착 성공하면 True 리턴한다.

if r - 1 >= 0 and not visit[r - 1][c + 1] and B[r - 1][c + 1] == '.':
    if dfs(r - 1, c + 1):
        return True

3방향 다 안 되면 False 리턴한다.

코드

# 백준 2109 - 빵집
# 분류 : DFS

R, C = map(int, input().split())
B = [list(input()) for _ in range(R)]
visit = [[False] * C for _ in range(R)]

def dfs(r, c) :
    visit[r][c] = True
    
    # 오른쪽 끝에 도달할 수 있으면 True else False
    if c == C - 1 :
        return True
    
    if r - 1 >= 0 and not visit[r - 1][c + 1] and B[r - 1][c + 1] == '.' :
        if dfs(r - 1, c + 1) :
            return True
    
    if not visit[r][c + 1] and B[r][c + 1] == '.' :
        if dfs(r, c + 1) :
            return True
        
    if r + 1 < R and not visit[r + 1][c + 1] and B[r + 1][c + 1] == '.' :
        if dfs(r + 1, c + 1) :
            return True
    
    return False

answer = 0
for i in range(R) :
    if dfs(i, 0) :
        answer += 1

print(answer)