[백준 3109번] 파이썬 - 빵집

백준 3109 - 빵집

시간 제한 1초, 메모리 제한 256MB

# 조건

• 유명한 제빵사 김원웅은 빵집을 운영하고 있다.
• 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.
• 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다.
• 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.
• 빵집이 있는 곳은 R * C 격자로 표현할 수 있다.
  • 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.
• 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다.
• 빵집과 가스관 사이에는 건물이 있을 수도 있다.
  • 건물이 있는 경우에는 파이프를 놓을 수 없다.
• 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다.
  • 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.
• 원웅이는 가스를 되도록 많이 훔치려고 한다.
  • 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다.
  • 이 경로는 겹칠 수 없고, 서로 접할 수도 없다.
  • 즉, 각 칸을 지나는 파이프는 하나이어야 한다.
• 원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)
• 다음 R개 줄에는 빵집 근처의 모습이 주어진다.
• '.'는 빈 칸이고, 'x'는 건물이다.
• 처음과 마지막 열은 항상 비어있다.

출력

• 첫째 줄에 원웅이가 놓을 수 있는 파이프 라인의 최대 개수를 출력한다.

# 접근 방법

• 제일 왼쪽 열에서 제일 오른쪽 열까지 파이프를 가장 많이 설치하면 된다.
• 이 때, 위에서 부터 아래로 탐색을 해줄 것이기 때문에 오른쪽 위, 오른쪽, 오른쪽 아래의 델타 함수 순서로 탐색을 해주는 것이 중요하다.
  • 오른쪽 위부터 설치하는 것이 아래와 겹칠 확률이 적기 때문이다.
• 이후, dfs 함수를 실행해준다.
  • dfs의 인자는 행 좌표와 열 좌표를 넣어준다.
  • 종료 조건은 j 좌표가 가장 오른쪽에 도착했을 때이다.
  • 파이프를 설치하여 연결된 곳이 배열을 벗어나지 않고 방문하지 않았다면, 재귀를 들어가준다.
  • 또한, dfs return이 False인 경우 파이프 설치 불가이므로 돌아가준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def dfs(i, j):  
    if j == C-1:  
        return True  
    for di in [-1, 0, 1]:  
        ni, nj = i + di, j + 1  
        if 0 <= ni < R and 0<= nj < C:  
            if bakery[ni][nj] != 'x' and not visited[ni][nj]:  
                visited[ni][nj] = True  
                if dfs(ni, nj):  
                    return True  
    return False  
R, C = map(int, input().split())  
bakery = [[*map(str, input().rstrip())] for _ in range(R)]  
visited = [[False] * C for _ in range(R)]  
answer = 0  
for i in range(R):  
    val = dfs(i, 0)  
    if val:  
        answer += 1  

print(answer)