본문 바로가기
반응형

그래프4

[백준] 13023번 - ABCDE (Java)(△) https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 인접리스트 방식으로 입력값을 저장한다. 2. 중복값을 값을 허용하지 않기 때문에 방문배열을 사용한다. 3. 친구관계는 A-B, B-C, C-D, D-E로 4개로 고정이 되어 있다. 따라서 호출 level이 5가 되면 친구관계를 다 찾은 것이다. 5. level == 5이면 더 이상 다른 친구관계를 찾을 필요없이(가지치기) 1을 출력하고 종료하면 된다. 6. 그래프의 시간복잡도 O(V + E)이므로 2,000 + 2,000 = 4,000, 모든 노드에 대한 탐색은 4,000 * 2,000 = 8,0.. 2023. 1. 26.
그래프의 표현방식 (인접 행렬 vs 인접 리스트) * 인접 행렬 import java.util.Scanner; /* 정점, 간선의 개수 이후 (노드, 노드, 비용)이 주어진 경우 5 6 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6 */ public class Graph { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // V = 정점의 개수, E = 간선의 개수. int V = sc.nextInt(); int E = sc.nextInt(); // 2차원 배열(인접 행렬)을 만든다. // 인덱스의 번호 = 노드의 번호 이기 때문에, 2차원 배열의 크기를 임의로 1 늘려서 정의한다(스킬). int[][] graph = new int[V + 1].. 2022. 10. 8.
[백준] 1987번 - 알파벳 (Java)(○) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. 세로 R, 가로 C로 된 맵이 있고, 대문자 알파벳으로 채워져 있음. 2. (1, 1)에 말이 있는데 상/하/좌/우로 움직일 수 있음. 그런데 이동한 칸의 알파벳은 이전 위치의 알파벳들과 달라야지 이동이 가능함. 3. 칸을 지날 때 마다 알파벳을 저장하는 배열이 필요하고, 새 알파벳과 비교하는 함수가 필요함. 4. 방문배열도 당연히 필요함. 5. dfs함수 파라미터는 좌표를 넘겨주자... 2022. 9. 2.
[백준] 11724번 - 연결 요소의 개수 (Java)(◎) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. 연결 요소의 개수는 연결된 정점 그룹의 개수라고 생각하면 된다. 2. 방향성이 없는 그래프이므로 인접행렬로 받도록 하자. 1. 그룹화를 만드는 것이 관건이다. 메인함수에서 dfs를 호출할 때 for문을 돌려서 정점 1번부터 N번까지 돌면서 호출하자. 2. 방문배열 visited[]를 적극 활용해서 이미 방문한 정점은 스킵하자. 조.. 2022. 8. 31.
반응형

티스토리툴바