[백준] 3109번 : 빵집

3109번: 빵집

3109번: 빵집

📄 문제개요

• 가스 배관을 설치 할 수 있는 경우의 수를 탐색하는 문제이다.
• 가장 오른쪽열에서 출발해서, 가장 왼쪽열로 도착 할 수 있는 경우의 수를 구해야한다.
• 가스배관 설치시에 겹처서 설치 되는 경우는 경우의 수에서 제외한다.

🤔 문제분석

• 그리디 문제로, 0번째 행에서 출발한다면, 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 무조건 탐색해야한다.
• R-1 번째 행에서 출발한다면, 오른쪽 아래, 오른쪽, 오른쪽 위 순으로 무조건 탐색해야한다.
• 깊이우선 탐색으로 우선순위에 맞는 순서로 탐색을 진행하여 도착 여부를 판단한다.

📝 의사코드

1. 행을 순회한다. (0~R-1) 열은 무조건 0으로 부터 시작한다. ( 빵집의 위치 )
2. 오름차순으로 순회함으로, 위의 조건인 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색한다.
3. 깊이우선으로 탐색하고, 3개의 Case에 대하여 탐색해나아간다. 만약 탐색해서 도착지에 도달 할 수 있다면, True 없다면 False 를 리턴 한다.
4. True라면 cnt 값을 증가시키고, False라면 무시한다.
5. cnt 값을 출력한다.

💻 코드

import sys
input = sys.stdin.readline

moves = [(-1, 1), (0, 1), (1, 1)] # 위, 중간 ,아래

R, C  = map(int, input().split()) # 행, 열
graph = [list(input().strip()) for _ in range(R)]

def dfs(i, j, graph):
    if j == C-1: # 도착지에 도달하면
        return True
    
    for dy, dx in moves:
        ny, nx = i + dy, j + dx
        if R > ny >= 0 and C > nx >= 0 and graph[ny][nx] != 'x':
            graph[ny][nx] = 'x' # 무조건 x처리 해준다. 왜냐하면, 갈 수 없는 경로를 또 체크하는 경우가 생기기때문이다.
            if dfs(ny, nx, graph): # 경로를 찾은경우 바로 return 한다.
                return True
    
    # 경로를 탐색 했는데 결과를 찾을 수 없을경우
    return False

ans = 0
for i in range(R):
    if dfs(i, 0, graph):
        ans += 1
        
print(ans)

🎯 피드백 및 개선사항

• 처음에는 BFS로 문제를 풀었다가, 시간복잡도 판정을 받게 되었다.
• 탐색할때 이미 갈 수 없는 경로가 존재하는데, 그 경로를 다른 이터레이션에서 한번더 탐색함으로서 시간복잡도 판정을 받았다.
• BFS로는 이터레이션에서 한번더 탐색 할 수 있는 조건을 구현하기 어려워, DFS로 변경 구현하였다.
• DFS로 구현할때, 우선순위 순서대로 방문하고, 방문한 그래프를 반드시 ‘x’로 업데이트 한다면, 또 다른 행의 리터레이션에서 재 방문하지 않는다.

❓다른사람은 어떻게 풀었을까?

• 스택 자료구조를 활용한 탐색으로 문제를 해결하신분이 있습니다.
• 일반적인 재귀 방식이 아닌 스택을 사용하여, 문제를 해결 하셨다.
• 재귀함수를 호출하는 cost를 절약하여 시간복잡도와 메모리 복잡도가 더 효율적이다.

import sys
r,c=map(int,sys.stdin.readline().split())
ml=[]
for i in range(r):
    ml.append(sys.stdin.readline().strip())
visited=[[False for _ in range(c)] for _ in range(r)]
cnt=0
xy=[1,0,-1]

for i in range(r):
    st=[]
    st.append([i,0])
    while(st):
        tmp=st.pop()
        col=tmp[0]
        depth=tmp[1]
        visited[col][depth]=True
        if depth==c-1:
            cnt+=1
            break
        for j in range(3):
            if 0<=col+xy[j]<r:
                if not visited[col+xy[j]][depth+1] and ml[col+xy[j]][depth+1]!="x":
                    st.append([col+xy[j],depth+1])
print(cnt)