본문 바로가기
728x90

BFS10

[백준 | Java] 1697번 숨바꼭질 1697번 / 숨바꼭질❓ 숨바꼭질🏷️ 관련 주제 : DFS BFS 시간복잡도 💦 나의 시도Try01. DFS재귀함수를 이용하여 DFS로 수빈이 이동한 점이 동생이 위치한 점과 일치하는지 탐색⏱️ 시간 초과작성했던 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static int limit; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe.. 2025. 1. 22.
[99클럽 5기] Day7 TIL - 자료형, BFS, DFS 99클럽 5기 | Java | Middler 🗝️ 오늘의 학습 키워드 : 자료형 BFS DFS ⌛ 회고오늘도 비기너 문제 먼저 풀고 미들러 문제를 풀었다.비기너 문제는 금새 풀었는데 미들러 문제는 1시간이 걸려도 풀리지 않았다.미들러 문제를 풀 때가 자정이 넘어갔을 때였기 때문에 피곤해서 일단 자고다음날 아침 문제의 풀이를 검색해 보았다.내가 시도한 방법은 BFS였는데 생각해 보니 DFS로도 풀 수 있을 것 같아서검색한 블로그의 풀이를 보지 않고 다시 시도해 보았다.채점의 퍼센트가 조금 더 올라가긴 했지만 시간 초과가 났다.검색한 반례 중, (1 100000)나 (10007 98767) 같은 입력을 할 때 시간이 오래 걸리던데시간을 줄일 방법을 아직 찾지 못해서 일단 TIL부터 올리기로 했다. ❓ 오늘.. 2025. 1. 22.
[백준 | Java] 1260번 DFS와 BFS 1260번 / DFS와 BFS❓ DFS와 BFS🏷️ 관련 주제 : Graph DFS BFS💦 나의 시도Try입력받은 두 정점 dot1, dot2에 대하여 int형 이차원 배열 graph[dot1 - 1][dot2 - 1], graph[dot2 - 1][dot1 - 1]에 1을 할당전체 배열을 탐색하려면 오래 걸릴 것 같아서 int[] minNum의 인덱스 i에 정점 i + 1에 연결된 최소 정점의 값을 할당DFS 실행지나간 정점을 체크하기 위해 ArrayList visited를 사용정점을 지날 때, visited에 해당 정점의 값을 추가BFS 실행큐(Queue)를 사용큐에 시작할 정점을 추가 후, BFS 탐색 시작큐에서 원소를 꺼내 해당 정점에 간선이 연결된 정점을 조회큐에서 꺼낸 원소는 visite.. 2025. 1. 21.
너비 우선 탐색(BFS; Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법시작 정점으로부터 가까운 정점을 먼저 방문멀리 떨어져 있는 정점을 나중에 순회깊게(deep) 탐색하기 전에 넓게(wide) 탐색 사용하는 경우두 노드 사이의 최단 경로 혹은 임의의 경로를 찾기 특징직관적이지 않음재귀적으로 동작하지 않음어떤 노드를 방문했었는지 여부를 반드시 검사해야 함.큐(Queue)를 사용방문한 노드들을 차례대로 저장한 후 꺼내는 자료구조선입선출(FIFO) 원칙으로 탐색일반적으로 큐를 이용해 반복적 형태로 구현'Prim', 'Dijkstra' 알고리즘과 유사 시간 복잡도인접 리스트로 표현된 그래프 : O(N + E)인접 행렬로 표현된 그래프 : $O(N^2)$희소 그래프(Spare Graph)의 경우,DFS.. 2025. 1. 21.
[99클럽 5기 | 자바 미들러] 6일차 TIL + Map, DFS, BFS 99Club 5기 | Java | Middler 🗝️ 오늘의 학습 키워드 : (비기너)문자열 Map HashMap / (미들러) Graph DFS BFS ⌛ 회고오늘은 조금 일찍 TIL 작성을 끝내려나 했는데비기너는 약간의 실수가 있었지만 해결했지만 미들러는 결국 한참 고민했지만 해결하지 못했다.사실 제출 시간이 거의 다 되어서 더 고민해 보지 못하고 그냥 인터넷에 풀이를 찾아보았다.오늘 다른 사람의 풀이를 찾아보면서 나 혼자 고민하는 것도 좋지만때로는 다른 사람의 풀이를 보면서도 배우는 것이 많구나!라는 생각이 들었다.앞으로는 99클럽에 권장 시간이라고 적힌 시간을 초과하면그냥 풀이에 내가 시도했던 방법만 작성해 두고 다른 사람의 풀이를 정리하고알고리즘 정리를 하면서 공부를 해야할 것 같다는 생각이 .. 2025. 1. 21.
[99클럽] 99클럽 코테 스터디 14일차 TIL + Tree, DFS 이전글  👈[99클럽] 99클럽 코테 스터디 13일차 TIL + Tree & DFSJava | Beginner🗝 오늘의 학습 키워드 : Tree Binary Tree DFS; Depth-First Search📚 공부한 내용 본인의 언어로 정리하기[LeetCode | Java | DFS  문제 풀이] 226. Invert Binary Tree - Solution with DFS⌛ 오늘의 회고 오늘 푼 Java | 비기너 문제는 주어진 트리를 반전하는 문제였다. left노드와 right노드의 TreeNode만 바꿔주면 되는 것이라 많이 어렵지 않았다. 이번주에 Binary Tree와 DFS 개념 정리를 못한 것이 너무 아쉽다.💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍📚 공부한 내용.. 2024. 6. 2.
[LeetCode | Java | DFS 문제 풀이] 226. Invert Binary Tree - Solution with DFS 99클럽 | 비기너🌲 226. Invert Binary Tree🏷 Topic : Tree DFS; Depth-First Search BFS; Breadth-First Search Binary TreeEasyGiven the root of a binary tree, invert the tree, and return its root.Example 1:Input: root = [4,2,7,1,3,6,9]Output: [4,7,2,9,6,3,1]Example 2:Input: root = [2,1,3]Output: [2,3,1]Example 3:Input: root = []Output: []Constraints:The number of nodes in the tree is in the range [0, 100.. 2024. 6. 2.
[LeetCode | Java | Tree 문제 풀이] 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree 99클럽 | Begginer🐾 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree🏷 Topic : Tree Binary Tree BFS DFSEasyGiven two binary trees original and cloned and given a reference to a node target in the original tree.The cloned tree is a copy of the original tree.Return a reference to the same node in the cloned tree.Note that you are not allowed to change any of the two trees or .. 2024. 5. 31.
[LeetCode | Java | DFS/BFS 문제 풀이] 938. Range Sum of BST - Solution with Recursion Function 99클럽 | Begginer938. Range Sum of BST 🏷 Topic : Tree Depth-First Search Binary Search Tree Binary Tree BFS DFSEasyGiven the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].Example 1:Input: root = [10,5,15,3,7,null,18], low = 7, high = 15Output: 32Explanation: Nodes 7, 10, and 15 are in the rang.. 2024. 5. 30.
728x90
⇧
Top

티스토리툴바