백준 3109번: 빵집 - 파이썬(greedy)

DFS알고리즘을 알고 있어야 풀 수 있는 문제다.

 

R,C로 행과 열의 값

pipe에 파이프라인 

visited에 파이프가 이미 설치되어 있는 곳인지 확인하기 위해 False로 초기화 리스트

이런 변수들을 입력 및 선언하고

 

왼쪽부터 시작해서 맨 오른쪽이 원웅이네 가게 파이프라인까지 최대한 많은 선을 연결해야 하므로

첫번째 열 에서 파이프라인이 있는 지점 pipe[i][0] == '.' 에서 부터 탐색을 시작한다.

solve함수를 호출하여 건물이 있는 지점을 피하며 오른쪽으로 이동하고, 방문했던 지점은 True로 흔적을 남긴다.

solve함수 종료조건인 j == C - 1 까지 도착하게 되면 True를 반환하여 cnt를 증가시킨다.

 

# 3109번 : 빵집
def solve(i,j):
    # 원웅이네 파이프로 무사히 도착하면 True 반환
    if j == C - 1:
        return True
    
    # DFS 알고리즘 이용
    for d in dx:
        if 0 <= i+d < R and pipe[i+d][j+1] == '.' and not visited[i+d][j+1]:
            visited[i+d][j+1] = True
            if solve(i+d, j+1):
                return True
    return False

R,C = map(int,input().split())
pipe = [list(input().rstrip()) for _ in range(R)]
visited = [[False] * C for _ in range(R)]
dx = [-1, 0, 1]
cnt = 0
for i in range(R):
    if pipe[i][0] == '.':
        if solve(i,0):
            cnt += 1
print(cnt)