[BOJ 3109, Python 3] 빵집

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

3109번: 빵집

골드2부터는 본격적으로 다른 스킬을 같이 쓰이는 문제들이 많이보이네요

이 문제는 그리디보다는 DFS에 치중된 문제 같습니다.

 

풀이

그리디 생각은 아주 간단합니다. 맨 위 좌표부터 확인하여 파이프들의 방향을 맨 위로 가게 우선순위를 설정하거나, 맨 아래 좌표부터 확인하여 맨 아래로 가게 우선순위를 설정하거나 둘 중 하나로 하면 됩니다.

일직선을 우선순위로 하면 안되는 이유, 맨 아래에서는 맨 아래 좌표부터 확인하고 맨 위에서는 맨 위 좌표부터 확인해야 하는 이유는 먼저 풀이를 설명하고 말하겠습니다.

 

이렇게 그리디적인 생각을 했으면 이제 DFS를 해주면 됩니다. 이때 주의할 점은 방문한 지점은 이제 더 이상 방문할 필요가 없으니 막아둬야 합니다.

왜냐하면 만약 파이프 라인을 만들 수 있으면 거긴 이제 파이프를 설치해서 벽으로 막는 것은 당연한 일입니다. 그리고 파이프 라인을 만들 수 없으면 해당 좌표로 움직여 DFS를 하는 것은 어차피 파이프 라인을 만들 수 없고 시간낭비만 하니까 막아둬야 합니다.

그래서 파이프 라인을 만들 수 있을 때와 없을 때 전부 더 이상 방문할 수 없도록 막아둬야 한다는 것을 알 수 있습니다.

 

일직선을 우선순위로 하면 안된다는 이유는 일직선으로 막아버리면 대각선으로 이동하여 파이프라인을 만들 수 있던 것도 못 만들게 하기 때문에 최적해를 구할 수가 없게 됩니다.

그리고 맨 위 좌표부터 확인하면 맨 위 방향을 우선순위로 하는 이유는 위쪽부터 확인해주면 DFS를 하는 동안 위쪽 공간이 비어있을 수도 있기 때문에 그렇습니다. 맨 아래 좌표부터 확인하면 맨 아래 방향을 우선순위로 하는 이유도 마찬가지 입니다.

 

코드

def go(x, y):
    arr[x][y] = 'x'
    if y == c - 1: return 1
    for nx in [x-1, x, x+1]:
        if 0 <= nx < r and arr[nx][y+1] == '.' and go(nx, y+1): return 1
    return 0
 
input = __import__('sys').stdin.readline
r, c = map(int, input().split())
arr = [[*input().strip()] for _ in range(r)]
print(sum(go(i, 0) for i in range(r)))