전체 글

문제 소개 BFS 풀이 직관적으로 보았을 때, 현재 셀을 기준으로 상하좌우로 이동하며 가능한 경로를 탐색하기 때문에 DFS나 BFS로 해결가능한 문제이다. 방문 조건 중 하나로 1인 칸으로만 이동이 가능하므로 1인 칸을 그래프에서의 하나의 노드로 볼 수 있기 때문이다. 다만 DFS로 풀었을 경우, 재귀적인 특성으로 인해 depth를 다루기가 까다롭다. 때문에 depth 대로 쭉 내려오는 것이 가능한 BFS를 사용하는 것이 더 간단한 풀이가 될 것으로 보인다. BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 바로 다음 깊이로 내려가는 식으로 동작하기 때문이다. 첫번째 출력 예시를 통해 예상되는 실행 결과를 확인해보았다. 시작점으로부터 출발하여 방문 가능한 셀들을 한 칸 씩 이동할때마다 1씩 증가시..

문제 소개 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. [선택된 노드의 거리 리스트 값 + 에지 가중치] < [연결 노드 거리 리스트 값..

Recurrent Relation(재귀 관계) 알고리즘에서 특정한 패턴이나 규칙에 따라 값을 반복적으로 계산하는 방법을 나타내는 수학/프로그래밍적 표현. 주로 재귀적인 방법을 사용하여 문제를 해결하거나 순환적인 구조를 다룰 때 사용 예시: 피보나치 수열 피보나치 수열은 재귀 관계를 사용하여 정의된다. F(n) = F(n-1) + F(n-2) ex) F(6)를 계산하려면 F(5)과 F(4)를 계산해야 하는 방식임. F(5)도 마찬가지이다. F(4)와 F(3)을 계산.. def fib(n: int) -> int: if n

문제 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가 몇인지를 기록해야함 -> 노드들 저장할 때 노드의 값 뿐만 아니라 노드가 ..