[코딩테스트/알고리즘] 그래프(Graph) - 그래프의 표현
이번 글에는 그래프를 표현하는 방법에 대해 알아보도록 하겠다. 정점 : {1, 2, 3, 4, 5, 6} 간선 : {(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 6), (4, 6)} 1. 인접 행렬 V개의 정점이 있을 때 V ☓ V 사이즈의 이차원 배열을 통해 나타낸다. 정점 i와 정점 j가 연결되어있을 때 A[i][j] = 1 정점 i와 정점 j가 연결되어있지 않을 때 A[i][j] = 0 예시 1 2 3 4 5 6 1 1 0 0 1 0 2 1 1 0 1 0 3 0 1 1 0 1 4 0 0 1 1 1 5 1 1 0 1 0 6 0 0 1 1 0 2. 인접 리스트 리스트(배열)를 이용해서 구현한다. 리스트는 크기를 동적으로 변경할 수 있어야 한..
2022. 12. 9.
[코딩테스트/백준 알고리즘] 13023번 - ABCDE (자바, Java 풀이)
문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 설명 문제 풀이 이 문제는 DFS를 통해 길이가 5인 경로가 존재하는지 확인하는 방법으로 해결할 수 있다. 하지만 이번 풀이는 다른 방법으로 해결해보겠다. 이 방법을 위해선 그래프를 표현하는 방법 중 인접 행렬, 인접 리스트, 간선 리스트를 모두 사용해야 한다. 간선 리스트를 사용해서 A - B 를 찾는다 간선 리스트를 사용해서 C - D 를 찾는다. 인접 행렬을 사용해서 B 와 C가 연결되어 있는지 확인한다. 입접 리스트를 사용해서 D에서 E(A, B, C, D가 아닌 친구)가 연결되어 있..
2022. 11. 1.
