[BOJ] 빵집 in Python

문제 풀러 가기!

문제를 읽다보면, 가장 위쪽 방향부터 찾으면 되겠다고 생각드는 문제였다.(이부분이 Greedy다)

사실 내 풀이는 최악의 시간복잡도가 1초 1억이 넘는다. Python이기 때문에..... 핸디캡이 붙은 듯 하다.

여튼 가장 위쪽 부터 탐색을 시도하면 그 다음 파이프라인은 이전에 만들어 놓은 파이프 라인 때문에 그 선으로 절대 갈 수 없으므로 이를 이용해서 DFS 탐색을 진행하면 된다. 이때 문제에서 요구한 c번째 열에 도착하면 파이프가 이어진 것이므로 이를 통해 파이프의 개수를 세면 되겠다.

DFS 알고리즘을 어떻게 짤 수 있나 생각이 들 수 있겠지만, toggle로 True False로 만든 뒤에 이를 계속 그 전 깊이로 넘기면 되겠다.

전체 코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(input().strip()) for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]

dx = [-1, 0, 1]
dy = [1, 1, 1]

def dfs(x, y):

    if y == c-1:
        return True

    toggle = False
    for i in range(3):
        nx, ny = x + dx[i], y + dy[i]
        if not (0 <= nx < r and 0 <= ny < c): continue
        if visited[nx][ny]: continue
        if board[nx][ny] == "." and not toggle:
            visited[nx][ny] = True
            toggle = dfs(nx, ny)

    return toggle

answer = 0
for i in range(r):
    visited[i][0] = True
    if dfs(i, 0):
        answer += 1

print(answer)