hyunkookim 님의 블로그

Graph -> 링크드리스트, 트리 둘다 포함 -> vertex (노드) 와 edge (연결방향)으로 구성 -> E    그래서,Tree와 linked list 는 방향성 있는 그래프(directed Graph) 라고 할 수 있고 방향성 없는 그래프(Undirected Graph) 라는 의미는,= 즉, 양방향 모두 갈수 있다는 의미= 양방향 에지(간선)=> matrix 행렬 또는 adjacency list 인접 리스트 를 사용해서 문제 품!! 1. 행렬(Matrix) 문제는?# Matrix (2D Grid)grid = [[0, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]] 0: Free1: Blocked 위에서 아래로 행..

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..

695. Max Area of Island BFS로 풀기from typing import Listfrom collections import dequeclass Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: # 섬 개수 및 최대 면적을 계산하는 함수 # Count the number of islands and calculate the maximum area # 네 방향 이동: 상, 하, 좌, 우 # Directions for movement: up, down, left, right directions = [[1, 0], [-1, 0], [0, 1], [..

200. Number of Islands https://youtu.be/pV2kpPD66nE?si=lYen92FEUHgGfFzQ class Solution: def numIslands(self, grid: List[List[str]]) -> int: # grid가 비어있으면 0을 반환 (예외 처리) # If the grid is empty, return 0 (edge case handling) if not grid: return 0 # grid의 행(Row) 수와 열(Col) 수를 변수에 저장 # Store the number of rows (ROWS) and columns (COLS) in variables ..

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. ..

547. Number of Provinces class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: # dfs 로.. # init n = len(isConnected) province = 0 visited = [False]*n def dfs(cur_node_number: int): visited[cur_node_number] = True for neighbor in range(n): if isConnected[cur_node_number][neighbor] == 1 and vi..