[백준] 3109번 : 빵집

안녕하세요. 오늘은 그래프 탐색 알고리즘 문제를 풀어보도록 하겠습니다.

 

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

3109번: 빵집

해당 문제는 깊이 우선탐색 + 그리디로 답을 도출 해낼 수 있습니다.

깊이우선탐색 : 한 위치에서 빵집까지를 갈 수 있는 경로를 탐색합니다.

 

1) 열이 위에서 아래 순서로 탐색해보는 조건

- 위에서 아래 순서로 탐색할때에는 우선순위를 오른쪽 대각선위 , 오른쪽, 오른쪽 대각선 아래 순서로 두어야 한다.

R, C = map(int, input().split()) # R은 행 C는 열
arr = []
visited = [[False for _ in range(C)] for _ in range(R)]

for i in range(R):
    char = str(input())
    arr.append(char)
    for j in range(len(char)):
        if char[j] == 'x':
            visited[i][j] = True
            
counter = 0

def dfs(i,j):
    global counter
    if R > i >=0 and C > j >=0 and not visited[i][j]:
        if j == C-1:
            counter +=1
            return True
        
        visited[i][j] = True
        if dfs(i-1,j+1): # 오른쪽 대각선 위
            return True
        if dfs(i,j+1): # 오른쪽
            return True
        if dfs(i+1,j+1): # 오른쪽 대각선 아래
            return True
    else:
        return False
    
for i in range(R):
    dfs(i,0)
     
print(counter)

2) 열이 아래에서 위 순서로 탐색해보는 조건

- 위에서 아래 순서로 탐색할때에는 우선순위를 오른쪽 대각선 아래 , 오른쪽, 오른쪽 대각선 위 순서로 두어야 한다.

R, C = map(int, input().split()) # R은 행 C는 열
arr = []
visited = [[False for _ in range(C)] for _ in range(R)]

for i in range(R):
    char = str(input())
    arr.append(char)
    for j in range(len(char)):
        if char[j] == 'x':
            visited[i][j] = True
            
counter = 0

def dfs(i,j):
    global counter
    if R > i >=0 and C > j >=0 and not visited[i][j]:
        if j == C-1:
            counter +=1
            return True
        
        visited[i][j] = True
        if dfs(i+1,j+1): # 오른쪽 대각선 아래
           return True
        if dfs(i,j+1): # 오른쪽
           return True
        if dfs(i-1,j+1): # 오른쪽 대각선 위
           return True 
    else:
        return False
    
for i in range(R,0,-1):
    dfs(i,0)
     
print(counter)