[Algorithm] 경로 탐색(그래프-인접리스트)
❐ 경로 탐색(인접리스트) ▶︎ 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. ▷ 입력 예제 5, [ [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5] ] ▶︎ 출력 예제 6 ▷ 문제설명 인접행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방법이다. 인접 행렬은 정점이 연결되어 있는지 확인하기 위해서 graph[a][b]의 요소만 확인할 수 있기 때문에 직관적이고 구현하기 쉽다는 장점이 있다. 하지만 구현해야 하는 그래프의 정점(vertex, 노드)의 개수가 10억개라면 어떨까..
2022. 10. 23.
[Algorithm] 경로 탐색(그래프-인접행렬)
❐ 경로 탐색(인접행렬) ▶︎ 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. ▷ 입력 예제 5, [ [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5] ] ▶︎ 출력 예제 6 ▷ 문제설명 그래프를 그려 문제를 해결해 보자. 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 문제의 그래프는 정점이 단순히 연결되어 있을 뿐 아니라 방향을 가리키고 있다. 예를 들어 1번 정점(vertex, 노드)은 2, 3, 4번 정점을 가리키고 있고, 1번과 2번 정점은 서로를 가리키..
2022. 10. 22.
