[백준 3109번] 빵집

import sys
input = sys.stdin.readline

r,c = map(int,input().split())

area = []

result = 0

for _ in range(r):
    area.append(list(input().strip()))

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

def dfs(x,y):
    global result

    area[x][y] = 'o'

    if y == c-1:
        result += 1
        return True
    
    for k in range(3):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < r and 0 <= ny < c: # 구역을 벗어나는지 확인
            if area[nx][ny] != 'x' and area[nx][ny] != 'o': # 지나갔던 곳이거나 건물이 있는 경우 제외
                if dfs(nx,ny):
                    return True

for i in range(r):
    dfs(i,0)

print(result)

보통 input()으로 문자열 값을 입력받지만 반복문으로 여러 줄을 입력받아야 할 때는 시간 초과 문제가 발생할 수 있다고 한다.
따라서 이럴 경우에는 import sys로 모듈을 불러오고 sys.stdin.readline()을 사용하는 것이 좋다.

이번 문제는 그리디 알고리즘만 이용해서 푸는 문제인줄 알았는데 DFS를 사용하지 않고 풀기엔 무리가 있었다. (골드문제 부터는 한가지 알고리즘만 요구하진 않는 것 같다 ..)

 

이 문제의 핵심인 오른쪽 대각선 위 - 오른쪽 - 오른쪽 아래 순으로 위에서부터 순차적으로 파이프를 연결한다는 것은 금방 알아챌 수 있었지만, DFS 문제를 아직 많이 풀어보지 못하여 제대로 구현해내지 못하였다.

 

다른 사람의 풀이를 참고하긴 했지만, DFS를 사용하여 '주어진 배열의 범위를 벗어나지 않도록 하는 것', '지나갔던 곳은 표시하여 다시 접근하지 못하도록 하는것', 'dx와 dy를 사용하여 효율적으로 탐색하는 것', '여러 줄을 입력받아야 할 때는 시간 초과를 피하기 위해 sys.stdin.readline()을 사용해야 하는 것'을 배울 수 있었던 문제였다 :)