hyunkookim 님의 블로그

✅ BFS (Breadth-First Search, 너비 우선 탐색)📌 정의BFS는 루트(또는 시작 노드)에서 가까운 노드부터 차례대로 방문하는 탐색 방식이에요.DFS는 한쪽 끝까지 파고들었다가(backtrack) 올라오는 방식이었다면,BFS는 먼저 “수평적으로” 넓게 퍼지면서 탐색해요.🧠 어떻게 동작하냐면?큐(Queue) 를 사용해요. → 선입선출 구조루트 노드를 큐에 넣고 시작큐에서 하나 꺼내서 처리하고, 그 노드의 자식들(또는 연결 노드들) 을 큐에 추가큐가 빌 때까지 반복📊 예시 (이진 트리 기준) 1 / \ 2 3 / \ \ 4 5 6BFS 순서: 1 → 2 → 3 → 4 → 5 → 6                  → 위에서부터, 왼쪽에서 오른쪽으로 한 층..

1091. Shortest Path in Binary Matrix 가장 짧은 경로 문제: BFS => 큐     cf) 목적지까지 갈수있는 경로 개수: DFS => 재귀 class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: N = len(grid) # n x n matrix if not grid: return -1 if grid[0][0] == 1 or grid[N-1][N-1] == 1: return -1 # shotedpath: using bfs, que def bfs(grid): q..

https://youtu.be/U4hFQCa1Cq0?si=qOfcXWT90Uo5RjvE  """# Definition for a Node.class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next"""class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': cur, nxt = root, root..

Binary Tree Right Side ViewSolved MediumYou are given the root of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.Example 1:Input: root = [1,2,3]Output: [1,3]CopyExample 2:Input: root = [1,2,3,4,5,6,7]Output: [1,3,7]CopyConstraints:0 -100 # Definition for a binary tree node.# class TreeNode:# def __init__(self, v..

102. Binary Tree Level Order Traversal # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: # root 없으면 return [] res = [] q = deque([r..

127. Word Ladder 이 문제는 "단어 변환"과 관련된 그래프 탐색 문제입니다. 주어진 시작 단어(beginWord)에서 끝 단어(endWord)까지 최소 몇 번의 단어 변환으로 도달할 수 있는지를 찾는 것입니다. 단, 변환 규칙은 다음과 같습니다:문제 규칙단어 변환 조건:변환 시 한 번에 한 글자만 변경할 수 있습니다.예를 들어, hit에서 hot으로는 변환 가능하지만, hit에서 dot으로는 한 번에 변환할 수 없습니다.변환 과정 제약:변환된 중간 단어는 반드시 wordList에 포함되어야 합니다.beginWord는 wordList에 없어도 변환 가능합니다.목표:beginWord에서 시작하여 endWord로 변환하는 가장 짧은 경로의 길이를 반환합니다.변환이 불가능한 경우 0을 반환합니다.입..

207. Course Schedule https://youtu.be/EgI5nU9etnU?si=bTi7R-EQNB2-fzZ2 class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 선수 과목 정보를 저장할 딕셔너리를 초기화합니다. # Initialize a dictionary to store prerequisite information. preMap = {i: [] for i in range(numCourses)} # prerequisites 리스트의 각 쌍 [course, pre]에 따라 preMap을 채웁니다. # Fi..

133. Clone Graph 이 문제는 연결된 무방향 그래프를 깊은 복사(deep copy)하라는 것입니다. 조금 더 쉽게 설명하자면, 그래프 전체를 복제하라는 것입니다. 그래프는 노드들로 이루어져 있고, 각 노드는 값(val)과 이웃 노드 목록(neighbors)을 가지고 있어요.핵심 포인트입력으로 주어진 그래프는 Node로 표현된 연결 그래프입니다.예를 들어, 노드 1은 Node(1)이고, 이웃 노드가 [2, 4]라면 Node(1).neighbors = [Node(2), Node(4)]와 같은 식으로 표현됩니다.이웃 노드가 연결된 그래프를 복사할 때, 모든 노드와 이웃 정보를 새로운 그래프로 깊은 복사를 해야 합니다.단순히 복사하는 것이 아니라, 새로운 메모리에 새로운 노드들을 만들어야 합니다.그래..

130. Surrounded Regions 이 문제에서는 주어진 m × n 크기의 보드에서 O로 이루어진 영역이 X로 둘러싸여 있는 경우,==> 해당 영역의 모든 O를 X로 바꾸는 것입니다.다만, 보드의 가장자리와 연결된 O는 둘러싸인 영역으로 간주하지 않으며 그대로 유지합니다.문제를 해결하기 위한 접근 방식가장자리와 연결된 O를 찾기:보드의 가장자리에서 시작하여, O로 이루어진 영역을 탐색하고, 해당 영역을 방문 처리합니다.이 과정에서 가장자리와 연결된 O는 둘러싸이지 않은 영역임을 표시합니다.O를 X로 바꾸기:보드 전체를 순회하며, 방문되지 않은 O는 둘러싸인 영역이므로 X로 바꿉니다.방문된 O는 가장자리와 연결된 영역이므로 그대로 유지합니다.탐색 방식:DFS나 BFS를 사용하여 O로 이루어진 영역을..

994. Rotting Oranges https://youtu.be/y_2x5llfqsE?si=ZrbbbsMQwGQ7Gt-o from collections import dequefrom typing import Listclass Solution: def orangesRotting(self, grid: List[List[int]]) -> int: fresh = set() # 신선한 오렌지 좌표를 저장 rotten = deque() # 썩은 오렌지 좌표를 저장 directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4방향 이동 rows, cols = len(grid), len(grid[0]) # 1. ..