![]()
들어가며 알고리즘 2주차의 1일차... 오늘의 회고는 짤 하나로 요약하고, 지난 그래프 알고리즘 DFS에 이어 BFS에 대해 TIL을 작성하고자 한다 그래프 탐색(순회) 깊이 우선 탐색(BFS, Breadth First Search) BFS는 특정 노드에서 시작해 인접한 노드를 먼저 탐색해나가는 방법으로, 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 쉽게 말하면, 그림처럼 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 방식으로 그래프를 순회하는 방법이다. BFS는 일반적으로 큐를 이용해서 지금 위치에서 갈 수 있는 곳들을 모두 큐에 넣는 방식으로 구현한다. 역시나 BFS도 예시를 들어가며 자세하게 설명해주는 글이 있어 첨부한다..
![]()
들어가며 본 포스팅은 책에서 다룬 리트코드 문제들을 다루고 있습니다. 문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다. 문제 Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may as..
