본문 바로가기

dfs8

[Java] DFS [Java] DFS 전위 순회 class Solution { public void DFS(int v) { if (v > 7) return; else { System.out.print(v + " "); DFS(v * 2); DFS(v * 2 + 1); } } public static void main(String[] args) { Solution T = new Solution(); T.DFS(1); } } // return : 1 2 4 5 3 6 7 중위 순회 class Solution { public void DFS(int v) { if (v > 7) return; else { DFS(v * 2); System.out.print(v + " "); DFS(v * 2 + 1); } } public stat.. 2023. 10. 12.
20230718 [Java] 문제풀이 20230718 [Java] 문제풀이 [백준] 1260 DFS와 BFS 예전에 파이썬으로 풀었던 문제를 자바로 풀어보았다 DFS와 BFS를 구현하는 것이다 여기서 만약에 자식 노드, 즉 다음 정점의 개수가 1개 이상일 경우, 제일 작은 것부터 탐색을 한다 즉 모든 자식 노드들을 오름차순으로 정렬을 해주면 된다 import java.util.*; public class baekjoon1260 { public static void dfs(int[] visited, ArrayList matrix, int start) { System.out.print(start + " "); visited[start] = 1; for (int i = 0; i < matrix.get(start).size(); i++) { if .. 2023. 7. 18.
[Java] 자료구조 - 그래프 [Java] 자료구조 - 그래프 그래프란? 정점 (Vertex, Node)와 간선 (Edge)로 이루어져 있다 트리, 이진트리도 그래프의 한 종류인다 그래프는 무방향 그래프와, 방향 그래프가 있다 무방향 그래프는 정점과 정점 사이에 방향이 없는 그래프이다 (즉 모든 정점들은 서로 왕복을 할 수 있다) 방향 그래프 같은 경우 정점에서 어느 정점으로 갈 수 있는 방향이 정해져 있다 (방향이 정해져 있으면, 그 방향 밖에 갈 수 없다) 정점 (Vertex) : 노드(Node)라고도 하고, 값 또는 데이터를 저장한다 간선 (Edge) : 정점을 연결하는 선이다 분지수 (차수, degree) : 무방향 그래프에서 하나의 정점과 연결되어 있는 간선의 수 내향 분지수 (진출 차수, in-degree) : 방향 그래프.. 2023. 6. 26.
[Python] 백준 14888 연산자 끼워넣기 🧑‍💻 [Python] 백준 14888 연산자 끼워넣기 Silver 1 - DFS DFS로 풀이를 했다 코드 min_num = 1e9 max_num = -1e9 N = int(input()) numbers = list(map(int, input().split())) operators = list(map(int, input().split())) def dfs(num_depth, total, plus, minus, multiply, divide): global min_num, max_num if num_depth == N: min_num, max_num = min(total, min_num), max(total, max_num) return if plus > 0: dfs(num_depth + 1, total.. 2023. 4. 7.
Udemy : 알고리즘 DFS, BFS, 백트래킹 Udemy : 알고리즘 DFS, BFS, 백트래킹 udemy 알고리즘 코딩 테스트 그래프 자료구조 그래프는 노드와 링크로 이루어진 자료구조다 노드는 점들이고, 노드를 이어주는 링크, Edge 또는 간선이라고 한다 SNS / 메신저 관계도를 그래프로 만들 수 있다 지도 / 네비게이션 같이 그래프를 실생활에 사용될 수 있다 무방향 또는 방향 그래프로 만들 수 있다 무방향이나 양방향 그래프는 동일한 개념이다 트리 자료구조 순환성이 없는 무방향 그래프다 코드를 그래프로 나타날 때에는 인접 리스트와 행열을 만들 수 있다 연결 행 연결 리스트 DFS (Depth First Search) 깊이 우선 탐색 스택 또는 재귀를 사용해서 구현을 한다 DFS는 완전 탐색이다 BFS (Breadth First Search) 너.. 2023. 3. 13.
[Python] 백준 1967 트리의 지름 🧑‍💻 [Python] 백준 1967 트리의 지름 Gold 4 - DFS 두 노드 사이의 가중치들을 더했을 때에 가장 큰 숫자를 출력하는 것 여기서 1의 기준에서 가중치가 제일 큰 노드를 구한다 그 다음, 가중치가 제일 큰 노드를 시작으로 DFS를 하여, 제일 큰 가중치를 구한다 여기서 DFS를 하면 어디서든, 제일 끝에 있는 자식 노드에 가게 된다 문제풀이 첫 DFS를 한 후에,visited 리스트 다시 초기화 시켜야 한다 second_index = visited.index(max(visited))을 통해서 두번째 DFS를 할 때에, 시작 점을 찾는다 코드 import sys sys.setrecursionlimit(10 ** 9) def dfs(start, weight): for node, wei in.. 2023. 2. 16.
[Python] 백준 1520 내리막길 🧑‍💻 [Python] 백준 1520 내리막길 Gold 3 - DFS DFS는 확실히 알았으나, 이걸 어떻게 DP로 풀어야 할지 몰랐다 1) 50 ▶️ 35 ▶️ 30 ▶️ 27 ▶️ 24 ▶️ 22 ▶️ 15 ▶️ 10 2) 50 ▶️ 45 ▶️ 37 ▶️ 32 ▶️ 20 ▶️ 17 ▶️ 15 ▶️ 10 3) 50 ▶️ 45 ▶️ 37 ▶️ 30 ▶️ 25 ▶️ 20 ▶️ 17 ▶️ 15 ▶️ 10 위를 보면, 15 ▶️ 10 은 3 경로 모두 겹친다 그리고, 20 ▶️ 17 ▶️ 15 ▶️ 10은 2번과 3번이 겹친다 겹치는 부분은 한번만 탐색을 하면 된다 즉 이미 방문을 했다면, 10까지의 경로는 겹치는 것이다 즉 겹치는 경로를 굳이 한번 더 탐색할 필요가 없다 코드 import sys sys.se.. 2023. 2. 15.
[Python] 백준 7576 토마토 🧑‍💻 [Python] 백준 7576 토마토 Gold 5 - BFS 무조건 BFS로 풀어야 하는 문제이다 시작점이 하나가 아닐 수 있다 그래서 queue 안에다 시작점들을 모두 찾아서 넣는다 BFS를 할때마다 주변 노드에다 방문 표시 대신 1을 더해서, 더한 숫자를 넣는다 마지막에 다시 탐색을 해야하는데, 0이 하나라도 있으면 -1을 출력하고, 그게 아니면 더한 숫자들 중 제일 큰 숫자에 1을 빼서, 답을 출력한다 문제풀이 bfs 식 주변을 탐색하고, 주변에 있는 노드 위주로 탐색하기 위해 popleft를 사용 첫 for문 queue에다가 시작 점들을 넣는다 시작점이 하나일 때에는 for문을 돌릴 필요가 없지만, 이 문제에서는 시작점이 1개 이상이 주어질 수 있다 두번째 for문 결과값을 탐색한다 bfs.. 2023. 2. 13.

티스토리툴바