본문 바로가기

728x90

dfs3

[BOJ] 2529번 - 부등호 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족하는 수열을 구해야한다. → 이 수열을 구하기 위해 백트래킹 방식을 사용한다. 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. → 백트래킹을 할 때 사용할 배열은 위와 같고 중복되지 않는 값들로 이뤄지도록 visited 배열을 사용한다. 이제 여기서 모든 부등호 관계를 만족하는 수열 중 가장 큰 값과 가장 작은 값을 구해야한다. 이때 주의할 점은 첫 자리가 0인 경우도 정수에 포함해야한다. 즉, 0123과 같이 출력해야한다. 나는 이를 쉽게 다루기 위해 문자열로 답을 구하기로 했다. 그러나 최솟값.. 2024. 3. 11.

[BOJ] 13023번 - ABCDE (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. - A는 B와 친구다. - B는 C와 친구다. - C는 D와 친구다. - D는 E와 친구다. 우선 여기서 알 수 있는 것은 N명 중 5명이 이와 같은 관계를 가지고 있으면 된다. 이러한 친구 관계를 구하기 위해서는 깊이 우선 탐색을 하여 구할 수 있다. 그래프의 깊이가 5이상일 경우 위와 같은 관계가 존재한다는 것을 알 수 있다. 단, 이는 판별만 하면 되기 때문에 관계를 발견하면 모든 탐색을 멈출 수 있도록 했다. 🍀 풀이 🍀 package Baekjoon; import java.io.*; import java.util.*; public class DFS13023 { sta.. 2024. 3. 1.

[graph] 깊이 우선 탐색(DFS, Depth First Search) 그래프 순회(Graph Traversal) 또는 그래프 탐색(Graph Search) 란? 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것 깊이 우선 탐색(DFS, Depth First Search) 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회방법 마지막 갈림길로 되돌아가야하므로 후입선출(Last-IN-First-Out) 구조인 스택(Stack) 사용 사실상 백트래킹과 똑같은 개념을 사용한다. DFS 수행 순서 스택이 공백이 될 때까지 빨간 상자 부분을 반복한다. DFS 과정 표현 ↓ ↓ ↓ ↓ ↓ ↓ ↓ .. 2023. 3. 6.

이전 1 다음

728x90

티스토리툴바