[BOJ] 3109. 빵집 (🥇, 그리디/DFS)

🔗

풀이

💡 아이디어

1열에서 C열까지 이동해야 한다. 가장 이상적이면서 파이프라인을 최대한 많이 설치할 수 있는 경우는 위의 그림과 같이 같은 행에 위치한 C열로 이동하는 것일 것이다. 하지만 중간에 건물들이 위치해있기 때문에 그림처럼 이상적으로 일렬로 나열되는 것은 어렵다.

대신 최적의 형태를 향해 갈 수는 있다. 최대한 출발하는 위치의 행과 같은 행에 있는 열로 이동하려고 하는 것이다.

방향은 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래라고 했다. 이때 건물에 의해 길이 비껴가야해서 아래쪽으로 내려가더라도 최대한 다시 위쪽으로 올라오려고 해서 출발한 지점의 행과 같은 행의 열로 이동하려고 한다면, 그림처럼 이상적인 형태로 갈 수 있다.

오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순서대로 이동할 것

위의 규칙을 지키며 예제2 번의 이동 경로를 그리면 위의 그림과 같다. 1행에서 이동하는 경우 3열에서 건물 때문에 아래로 내려가게 되지면 4열에서 대각선 위로 먼저 이동하였고 결국 최종적으로 1행 C열에 도달하면서 종료된다. 이렇게 위쪽에서부터 차례대로 출발 지점의 행에 있는 C열에 도달하려고 하면 가장 첫 번째 그림의 이상적 형태를 유지할 수 있고, 아래의 행들도 최대한 출발 지점의 행에 위치한 C열에 도달할 수 있는 확률이 높아진다.

⏰ 시간 초과

근데 시간 초과가 났다.

기존 풀이에서는 이동하는 경로를 DFS로 구했는데, 경로를 이동하면서 계속해서 방문처리를 했다. 하지만 C열에 도달할 수 없는 경로들의 경우에는 방문처리를 False 로 변경해서 아래에 있는 행들 역시 해당 경로를 통해 한 번 더 이동할 수 있는 기회를 줘서 최대한 많은 파이프라인을 설치하려고 했다.

하지만 어차피 한 번 C열에 도달할 수 없다고 판단된 위치는 다른 어떤 위치에서 출발해서 그 위치에 도달하더라도 똑같이 C열에 도달할 수 없다.

위의 그림에서 빨간 점은 결국 최종적으로 C열에 도달할 수 없다. 이미 2번째 행에서 판단되었지만, C열에 도달하지 못했기 때문에 방문처리가 False 로 변경되어 있고 그렇기 때문에 3번째 행에서 다시 해당 위치를 통해 2번째 행에서 지나쳤던 경로를 다시 지나치게 된다.

결국 이미 안 된다고 판명된 위치를 계속 반복해서 방문하는 불필요한 중복과정이 있었기 때문에 시간초과가 난 것이다.

# 빵집

import sys
input = sys.stdin.readline

def dfs(x, y):
    global way
    visited[x][y] = True
    if y == C - 1:
        way += 1
        return True
    
    for k in range(3):
        nx, ny = x + DIR[k][0], y + DIR[k][1]
        if (nx < 0 or nx >= R or MAP[nx][ny] == 'x' or visited[nx][ny]): continue
        if dfs(nx, ny):
            return True
    # visited[x][y] = False
    return False

R, C = map(int, input().split())
MAP = [list(input()) for _ in range(R)]
visited = [[False] * C for _ in range(R)]
DIR = [(-1, 1), (0, 1), (1, 1)]
way = 0

for i in range(R):
    visited[i][0] = True
    dfs(i, 0)

print(way)