소피it블로그

https://leetcode.com/problems/flood-fill/ Flood Fill - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 분명 어려운 문제는 아닌데 아직도 bfs에 완전히 익숙해지지가 않아서 꽤 헤맸다. 특히, dx, dy로 리스트를 만들어놓고 다른 노드를 방문하는 방법이 아직 익숙하지 않아 우선은 중복되고 장황한 while문을 썼다. 또한, 처음에는 visited 리스트를 따로 만들려고 했으나, 풀다보니 굳이 그럴 필요 없이 방문한 곳의..

https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com from collections import deque class Solution: # grid, m, n은 bfs함수와 numIslands함수에서 모두 참조할 수 있도록 클래스 변수로 선언 grid: [[str]] m: int n: int def bfs(self, start_i, start_j)..

1. BFS: Breadth-First Search 너비 우선 탐색 BFS에서는 큐를 활용한다. 너비 우선 탐색이라는 개념과 FIFO의 특징을 생각해 보면 쉽게 이해할 수 있다. 큐를 사용하여 큐에 먼저 들어간 노드들을 먼저 팝해주는 것. from collections import deque def bfs(graph, node, visited): queue = deque([node]) # 첫 번째 노드로 큐를 만들어줌 visited[node] = True # 해당 노드 방문 기록 while queue: # 큐에 요소가 남아있는 동안 n = queue.popleft() # 큐의 앞에서 요소 빼줌 print(n, end = " ") # 해당 요소 출력 for i in graph[n]: # 해당 요소의 자식 ..