[백준] 빵집 3109번 Python

문제

빵집
원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

 

첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)

다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.

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

문제 생각 & 풀이

주요 아이디어는 첫 번째 열에서 시작하여 마지막 열에 도달하는 가능한 모든 경로를 탐색하는 것이었다.
각 경로는 겹치지 않아야 하며, 건물이 있는 칸은 지나갈 수 없다.

1. 방향의 우선순위를 오른쪽 위 대각, 오른쪽 중간, 오른쪽 아래 대각으로 시작

2. 탐색 중 방문한 칸은 즉시 건물로 표시('x')하여 다른 경로에서 다시 방문하지 않도록 함.

3. 이전 경로에서 가지 못한 길이라면, 이후 경로에서도 가지 못할 것이므로 방문 표시를 따로 해주지 않아도 되었음.

 

위의 3가지 방법을 기반으로 DFS를 활용하여 풀 수 있었다.

 

CODE

import sys
input = sys.stdin.readline

def solve(y, x):
  arr[y][x] = 'x' # 'x'로 방문표시

  # 파이프라인 : 항상 첫번째 열에서 시작해서 마지막 열에서 끝나야함
  # 현재 위치가 마지막 열 바로 전이면 연결 성공
  if x == C-2:
    return True

  # 첫 번째 행에서는 위로 이동 못함 y > 0
  if y > 0 and arr[y-1][x+1] != 'x': # 오른쪽 위 대각선
    if solve(y-1, x+1):
      return True

  if arr[y][x+1] != 'x': # 오른쫃 중간
    if solve(y, x+1):
      return True

  # 마지막 행에서는 아래로 이동 못함 y < R-1
  if y < R-1 and arr[y+1][x+1] != 'x': # 오른쪽 아래 대각선
    if solve(y+1, x+1):
      return True

  # 위 조건 다 실패하면 False
  return False

R, C = map(int, input().strip().split())
arr = [list(input().strip()) for _ in range(R)]

res = 0 # 최대 파이프라인 개수
for i in range(R):
  if solve(i, 0):
    res += 1

print(res)