[백준] 3109번 빵집 파이썬

문제링크: https://www.acmicpc.net/problem/3109

난이도: GOLD II

문제해결 아이디어

• 위쪽부터 탐색해야 최대한 많은 파이프설치 가능 (그리디)
• 재귀 종료조건: 마지막 열에 도달하는지 여부
• 파이프 끼리 겹쳐서 다시 방문 못하거나 해당 좌표에서는 파이프를 연결할 수 없거나 둘 중에 하나 이므로 다시 '.'으로 만들 필요가 없다.

소스코드

import sys

input = sys.stdin.readline

n,m = map(int, input().split())

board = []

for _ in range(n):
    board.append(list(input().strip()))

dx = [-1,0,1] #위쪽부터 탐색해야 최대한 많은 파이프설치 가능 (그리디)

cnt = 0

def dfs(x,y):
    if y == m-1: #재귀 종료조건: 마지막 열에 도달하는지 여부
        return True

    for i in range(3):
        nx = x + dx[i]
        ny = y + 1

        if 0<=nx<n and 0<=ny<m and board[nx][ny] == '.': 
            board[nx][ny] = 'x' # 파이프 끼리 겹쳐서 다시 방문 못하거나 해당 좌표에서는 파이프를 연결할 수 없거나 둘 중에 하나 이므로 다시 '.'으로 만들 필요가 없다.
            if dfs(nx, ny):
                return True

    return False

for i in range(n):
    if dfs(i, 0):
        cnt +=1

print(cnt)