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

풀이

원웅이의 빵집이 있는 마지막 열 c - 1부터 시작해서 0번째열까지 도착했을 때 가스관이 연결되어 있다고 할 수 있음. x == 0일 때 count += 1
최단 거리로 설치해야 하려면 x축은 -1방향으로만 이동, 가스관은 대각 방향으로도 설치가 가능하기 때문에 y축은 -1, 0, 1로 이동 가능
그리고 가능한 위치 중 y좌표가 작은 위치에 설치하는 것이 가능한 더 많이 설치할 수 있으므로 순회 순서를 direction = [(-1, -1), (-1, 0), (-1, 1)]로 설정
방문한 위치를 'x'로 변경하면서 가능한 위치를 dfs로 순회.
파이프가 다른 빵집에 도달하게 된다면 순회 종료.
if dfs(nx, ny): return True 이 부분은 결국 다른 풀이를 참고했다.

코드

import sys
sys.setrecursionlimit(int(1e8))

input = sys.stdin.readline

r, c = map(int, input().split())
maps = [list(map(str, input().rstrip())) for _ in range(r)]
count = 0
direction = [(-1, -1), (-1, 0), (-1, 1)]
def dfs(x, y):
    global count
    if x == 0:
        count += 1
        return True

    for dx, dy in direction:
        nx, ny = x + dx, y + dy
        if 0 <= nx and 0 <= ny and ny < r and maps[ny][nx] == '.':
            maps[ny][nx] = 'x'
            if dfs(nx, ny):   
                return True
    return False

for y in range(r):
    dfs(c - 1, y)

print(count)