BOJ 3109 - 빵집

문제

백준 온라인 저지 - 3109번

풀이 과정

파이프를 연결할 수 있는 세 가지 방법을 이용해서 가장 많은 연결 방법을 찾는 문제입니다.
백트래킹 을 이용해서 모든 경우를 찾을 수 있는데 문제는 중복된 탐색이 많이 존재한다는 것입니다.

여기서 얻을 수 있는 아이디어는 백트래킹 을 통해 한 지점에서 목표 지점에 도달하는 방빕이 있는지 판단하고 있다는 것입니다.
따라서 현재 지점에서 목표 지점에 방문이 가능하지 않더라도
이 지점을 다시 미방문 상태로 바꿔주는 것이 아니라 그냥 방문 처리로 남겨놔도 됩니다.
(목표 지점에 도달 가능한 경우는 이 경로에 파이프를 놔야하기 때문에 방문 처리를 합니다.)
왜냐하면 이후에 해당 지점에 다시 방문하더라도 또 다시 목표 지점에 도달 불가능한 것은 자명하기 때문입니다.
이를 통해서 중복된 탐색 횟수를 줄일 수 있습니다.

처음에는 이 문제가 왜 그리디 로 분류되어 있는지 몰랐는데 중복 탐색을 줄이는 아이디어 때문에 이렇게 분류된 것 같습니다. 😄

코드

import sys

sys.setrecursionlimit(10**6)

R, C = list(map(int, sys.stdin.readline().split()))
board = [list(sys.stdin.readline().strip()) for _ in range(R)]


def dfs(r, c):
    global board

    board[r][c] = 'x'

    if c == C - 1:
        return True

    is_reachable = False
    for nr, nc in [[r - 1, c + 1], [r, c + 1], [r + 1, c + 1]]:
        if nr < 0 or nr >= R or nc >= C:
            continue

        if board[nr][nc] == '.':
            is_reachable = is_reachable or dfs(nr, nc)

    return is_reachable


def solution():
    answer = 0

    for r in range(R):
        is_reachable = dfs(r, 0)
        if is_reachable:
            answer += 1

    return answer


print(solution())