[백준]3109 빵집 #그리디#dfs

1. 풀이

(1) 0열(빵집)에서 가장 윗 행부터 차례대로 출발하여 (오른쪽위,오른쪽,오른쪽아래) 순서대로 파이프를 놓는다.

(2) 끝열(원웅이집) 까지 놓을 수 있으면 최종답 +1후 종료, 놓을자리가 없으면 그자리에서 종료

(3) 이때 방문했던 곳은 다시 방문할 수 없으므로 표시해준다. (끝열(원웅이집)까지 못가더라도 윗행에서 못가면 아래에서도 못가기 때문에 visited로 표시해준다)

* 파이프를 최대한으로 설치하기 위해선 무조건 (우상,우,우하) 순으로 진행되고, 윗행에서 부터 아래행으로 내려오면서 탐색하면 반드시 최적해가 나오는 그리디 문제이다. 또한 파이프를 최대로 만들기 위해선 엇갈리는 경우도 배제해야 한다.

( 커플만들기 문제와 비슷 https://sosoeasy.tistory.com/40)

 

2. 소스코드

dR = [-1, 0, 1]
dC = [1, 1, 1]

R, C = map(int, input().split())

L = []
for i in range(R):
    L.append(list(input()))


def dfs(r, c):
    if c == C - 1:
        return True

    for k in range(3):
        tempR = r + dR[k]
        tempC = c + dC[k]
        if 0 <= tempR < R and L[tempR][tempC] == ".":
            L[tempR][tempC]="o"
            if dfs(tempR, tempC):
                return True

    return False

ans = 0
for i in range(R):
    ans += dfs(i, 0)
print(ans)