[백준알고리즘] 3109번: 빵집 -Python

[백준알고리즘] 3109번: 빵집 -Python

https://www.acmicpc.net/problem/3109

3109번: 빵집

문제에 대한 접근은 어렵지 않은 것 같다. visit 리스트를 만들고 오른쪽 위부터 우선적으로 이동하면서 윗줄부터 가능한 경우를 채워나가면 된다.

 

하지만 처음에 시간 초과가 나왔다. 문제는 하나의 위치에 중복해서 방문하는 것이었다. 항상 solve()의 결과가 False이면 visit[][]의 값을 False로 바꿔주었는데, 그럴 필요가 없었다.

 

한번 해당 지점을 방문해서 원웅이의 빵집에 도달했으면 이미 연결된 경로이기 때문에 파이프를 둘 수 없는 지점이 되며, 해당 지점을 방문한 이후 원웅이의 방집까지 도달하지 못했으면 또다시 해당 지점에 방문했을 때도 마찬가지로 원웅이의 빵집까지 도달할 수 없기 때문이다.

def solve(i, j):
    if j == c-1:
        return True
    
    for d in dx:
        if 0<=i+d<r and table[i+d][j+1] == '.' and not visit[i+d][j+1]:
            visit[i+d][j+1] = True
            if solve(i+d, j+1):
                return True
    return False

r, c = map(int, input().split())
table = [list(input().rstrip()) for _ in range(r)]
visit = [[False] * c for _ in range(r)]
dx = [-1, 0, 1]
ans = 0
for i in range(r):
    if table[i][0] == '.':
        if solve(i, 0):
            ans += 1
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다