dfs
-
200. Number of IslandsProgramming/leetcode 2021. 2. 24. 15:09
DFS(재귀)를 이용한 문제 풀이 좌표를 찾아가다가 1을 만나면 연결된 1을 0으로 만들고 상,하,좌,우에 1이 없을때까지 반복 내부함수로 구현했지만, dfs를 함수로 빼도되지만, self와 grid를 넘기기 싫어서 이렇게 구현함 def numIslands(self, grid: List[List[str]]) -> int: def dfs(x:int, y:int)->int: if x = len(grid) or y = len(grid[0]) or grid[x][y] != '1': return 0 grid[x][y] = 0 dfs(x+1, y) dfs(x-1, y) dfs(x, y+1) dfs(x, y-1) return 1 count = 0 for i in range(len(..
-
DFS, BFSProgramming/leetcode 2021. 2. 23. 22:44
그래프 순회 이론 정리 DFS - 깊이 우선 탐색, Stack과 재귀 호출로 구현되며 Back-Tracking과 같이 사용하면 뛰어난 효과 BFS - 너비 우선 탐색, 주로 Queue로 구현하며 최단 경로 문제에서 많이 사용됨(다익스트라 알고리즘) 코딩테스트에서 대부분의 그래프 탐색은 DFS로 이루어짐 DFS - Stack과 재귀 호출로 구현 ex) graph = { 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:3} 재귀 호출로 구현 graph = { 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:[3]} def recursive_dfs(v, discovered=[]): discovered.append(v) for w in ..