문제 소개 DFS 맨 아랫줄까지 제한된 방향 수의 연산을 반복적으로 실행해야 될 것으로 파악되어 재귀적인 방법을 떠올렸다. 가능한 모든 경우의 수를 살펴보고자 DFS로의 접근을 시도하였다. def dfs(i, j, total_sum): if i == test_cases - 1: total_sum = max(total_sum, arr[i][j]) else: left = dfs(i + 1, j, total_sum) right = dfs(i + 1, j + 1, total_sum) route1 = arr[i][j] + left + total_sum route2 = arr[i][j] + right + total_sum total_sum = max(route1, route2) return total_sum tes..
문제 You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. i..
앞서 다익스트라 알고리즘에 대한 개념을 익혀보았으니 최단 거리 구하는 문제들을 몇 가지 살펴보자 방식 1. Priority Queue 모듈을 사용 BOJ 1753 import sys from queue import PriorityQueue input = sys.stdin.readline # 노드, 에지 개수 V, E = map(int, input().split()) # 출발 노드 K = int(input()) # 거리 리스트 (노드 갯수보다 한 개 많게 설정(노드 1부터 시작하게끔)) distance = [sys.maxsize] * (V+1) # 충분히 큰 값으로 초기화 # 방문 여부 저장 리스트 visited = [False] * (V+1) # 에지 데이터 저장 인접 리스트 (그래프) myList = ..
다익스트라 알고리즘은 그래프 상 시작 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘. (그래프 간선의 가중치가 항상 양의 정수 값이어야 함.) 시간 복잡도 : O(ElogV) => V: 노드 개수, E: 에지(간선) 개수 개념 이해를 위해 그래프를 하나 예시로 들어보자 각 노드에서 향하는 정점과 가중치를 인접리스트로 정리해보았다. 1. 출발 노드를 설정하고, 그를 제외한 나머지 노드들을 INF(무한대) 값으로 초기화한다. 2. 거리 리스트에서 아직 방문하지 않은 노드 중 가장 작은 노드를 선택(우선순위 큐에서 데이터 뽑아옴) 연결된 노드들의 최단 거리값을 공식을 이용해 업데이트 (테이블 갱신) 3. [선택된 노드의 거리 리스트 값 + 에지 가중치] < [연결 노드 거리 리스트 값..
문제 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 assume all four edges of the grid are all surrounded by water. 섬은 수평과 수직으로 땅이 연결되어있고, 물로 둘러싸여있는 것으로 가정함. 또한 grid 네개의 가장자리는 모두 물로 둘러싸여있다는 것을 가정. 제약조건 m == grid.le..
문제 Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 주어진 이진트리의 최대 깊이를 찾는 문제 레벨 오더는 BFS와 유사한 방식으로 구현이 됨. 일단 queue로 시작하여 첫번째 root 노드에 대해 큐에 인큐를 함(이 노드에 곧 방문할 예정이라는 의미) 왼쪽 오른쪽에 있는 하위(child) 노드들에 대해 level by level로 방문 depth가 몇인지를 기록해야함 -> 노드들 저장할 때 노드의 값 뿐만 아니라 노드가 ..
