[HackerRank] Count Luck

def countLuck(matrix, k):
    
    row = len(matrix)
    col = len(matrix[0])
    nx = [-1,1,0,0]
    ny = [0,0,-1,1]
    start_x, start_y = 0, 0
    
    count = 0
    
    graph = []
    for i in range(row):
        graph.append(list(matrix[i]))
    
    for i in range(row):
        for j in range(col):
            if graph[i][j] == 'M':
                start_x, start_y = i, j
    
    # Write your code here
    def dfs(area, x, y):
        # visited[x][y] = True
        
        if area[x][y] == '*':
            return True
            
        direct_count = 0
        
        for i in range(4):
            temp_x = x + nx[i]
            temp_y = y + ny[i]
            
            if temp_x >=0 and temp_x < row and temp_y >=0 and temp_y < col:
                if area[temp_x][temp_y] == '.' or area[temp_x][temp_y] == '*':
                    direct_count += 1
                    
        if direct_count > 1:
            area[x][y] = '1'
        else:
            area[x][y] = '0'
            
        for i in range(4):
            temp_x = x + nx[i]
            temp_y = y + ny[i]
            
            if temp_x >=0 and temp_x < row and temp_y >=0 and temp_y < col:
                if area[temp_x][temp_y] == '.' or area[temp_x][temp_y] == '*':
                     if dfs(area,temp_x,temp_y):
                        return True
        area[x][y] = '.'
        
        return False
            
    dfs(graph,start_x,start_y)
    
    for i in range(row):
        for j in range(col):
            if graph[i][j] == '1':
                count += 1
    
    if count == k:
        return "Impressed"
    else:
        return "Oops!"

이번 문제는 주어진 행렬(matrix)에서 시작지점('M')에서 도착지점('*')까지의 경로 중에서 선택할 수 있는 경로가 2개 이상인 좌표의 수를 구하는 문제이다.
 
문제를 해석해보면 결국 도착지점까지 이동하면서 wand를 사용하는 경우라는 의미는 즉, 해당 위치에서 이동할 수 있는 경로가 2가지 이상인 경우를 의미한다.
 
먼저 문제에서 주어진 것처럼 지나가는 경로마다 '0'(wand를 사용하지 않는 경우)과 '1'(wand를 사용하는 경우)를 기록한다면 사용 여부를 저장하는 vistied을 사용할 필요가 없다.
 
DFS 알고리즘을 사용해서 도착지점까지 경로를 찾으면 되는데, 이때 문제의 조건 중 도착지점까지의 경로가 단 1가지라는 조건이 존재하기 때문에 도착지점까지의 경로가 아닌 경로는 0과 1로 채워진 위치를 다시 '.'으로 되돌려 주어야 한다.
 
따라서 dfs함수에서 return 하기전에 자신의 위치를 다시 '.'으로 되돌려놓고, 도착지점에 도착한 경우에는 바로 True를 반환하였다.
👉🏻 이렇게 True/False를 리턴하게 되면 모든 경로에서 True를 리턴하면 되므로 도착지점까지의 경로를 파악할 수 있다. ⭐️
 
DFS 알고리즘을 새로운 방법으로 풀이해보는 좋은 문제였다 :)