2023.06.02 Today's Challenge

fabichoi 2023. 6. 2. 23:45

https://leetcode.com/problems/shortest-path-in-binary-matrix/solutions/

Shortest Path in Binary Matrix - LeetCode

Can you solve this real interview question? Shortest Path in Binary Matrix - Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path in a binary matrix is a path from

leetcode.com

예상대로 DFS로 푸는 문제!

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        gr = collections.defaultdict(list)
        n = len(bombs)

        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                xi, yi, ri = bombs[i]
                xj, yj, _ = bombs[j]

                if ri ** 2 >= (xi - xj) ** 2 + (yi - yj) ** 2:
                    gr[i].append(j)
        
        def dfs(cur, visited):
            visited.add(cur)
            for neib in gr[cur]:
                if neib not in visited:
                    dfs(neib, visited)
            return len(visited)
        
        answer = 0

        for i in range(n):
            visited = set()
            answer = max(answer, dfs(i, visited))
        
        return answer