분류 전체보기45 [BOJ] [JAVA] 2252번 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬 문제다. 사이클이 없는 방향 그래프의 모든 노드들을 순서에 맞춰 정렬하는 알고리즘이다. 노드에 들어오는 간선의 개수인 진입차수가 0인 노드들은 수행할 수 있는 상태의 노드들이므로 큐에 넣는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; .. 2024. 2. 20. [알고리즘] [16] 그래프 순회2 1. DFS 시작 지점의 한 방향으로 갈 수 있는 경로까지 깊이 탐색하다가 더 이상 갈 수 없을 때 이전 갈림길 간선으로 되돌아가 다른 정점을 탐색하는 순회 방법 재귀적으로 혹은 스택 자료구조를 이용하여 구현한다. 인접 행렬 또는 인접 리스트를 적절히 사용하여 DFS를 구현한다. 2. Flood Fill 알고리즘 플러드 필 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림 프로그램에서의 '채우기' 도구 또는 지뢰 찾기 등에 사용된다. 4방향 델타 배열 혹은 8방향 델타 배열을 사용할 수 있다. DFS 혹은 BFS로 구현된다. 3. 위상 정렬 (Topology Sort) 유향 그래프의 정점들을 간선의 방향을 거스르지 않도록 나열하는 것 순서가 정해진 작업들.. 2024. 2. 20. [BOJ] [JAVA] 1238번 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 그래프의 정점과 간선이 주어지고 각 정점에서 특정 정점(파티)까지 갔다가 되돌아는 최단거리 중 최댓값을 구하는 문제다. 다익스트라 알고리즘을 활용해서 해결할 수 있었다. 다익스트라는 임의의 시작점에서부터 다른 노드로 가는 최단거리를 구할 수 있는 알고리즘이다. 다이내믹 프로그래밍과 유사하다고 느꼈다. dp의 일종인가? 그래프를 두 가지로 동시에 입력받았다. 하나는 입력 그대로의 그래프 (파티에서 각자의 집으로 돌아갈 때 다익스트라를.. 2024. 2. 16. [알고리즘] [15] 그래프 순회 1. 그래프 순회 비선형 구조인 그래프의 모든 정점을 빠짐없이 탐색하는 것 너비 우선 탐색과 깊이 우선 탐색으로 순회할 수 있다. 2. BFS (Breadth First Search) 탐색 시작점의 인접 정점을 모두 방문한 이후, 방문한 정점을 시작점으로 하여 차례로 방문한다. 그래프는 계층형 구조가 아니기 때문에 루트의 개념이 없어 임의의 정점에서 시작 가능하다. 선입선출 형태의 큐를 활용한다. 2024. 2. 16. 이전 1 2 3 4 5 ··· 12 다음