책/Do it! 알고리즘 코딩 테스트 자바 편
Day-14 그래프의 표현
댈팽이
2024. 4. 10. 21:54
728x90
1. 에지 리스트
- 에지를 중심으로 그래프를 표현한다.
- 구현이 쉽다.
- 특정 노드와 관련되어 있는 에지를 탐색하기가 어렵다.
- 벨만 포드, 크루스칼 알고리즘에 사용한다.
가중치가 없는 그래프인 경우 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.
1에서 2로 가는 에지는 [1, 2]로 표현한다.
가중치가 있는 그래프인 경우 배열에 출발 노드, 도착 노드, 가중치를 저장하여 에지를 표현한다.
1에서 2로 가는 가중치가 8인 에지는 [1, 2, 8]로 표현한다.
2. 인접 행렬
- 2차원 배열을 자료구조로 이용하여 노드 중심으로 그래프를 표현한다.
- 구현이 쉽다.
- 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
- 노드 개수가 많은 경우 사용할 수 없다.
노드 개수가 5이므로 5 x 5 행렬을 사용한다.
1에서 2로 가는 에지는 A[1][2]에 1을 저장하여 표현한다.
가중치가 없는 그래프이므로 가중치 대신 1을 저장한다.
가중치가 있는 그래프이면 1 대신 가중치를 저장한다.
1에서 2로 가는 가중치가 8인 에지는 A[1][2]에 8을 저장하여 표현한다.
3. 인접 리스트
- ArrayList로 그래프를 표현한다.
- 구현이 복잡하다.
- 공간 효율성이 좋다.
노드 개수인 5만큼 ArrayList를 선언한다.
1과 연결된 노드 2, 3을 ArrayList[1]에 [2, 3]을 연결하여 표현한다.
가중치가 있는 그래프인 경우 도착 노드, 가중치를 갖는 Node 클래스를 사용한다.
1과 연결된 노드 2, 3을 ArrayList[1]에 [(2, 8), (3, 3)]을 연결하여 표현한다.
4. 예제 문제
[2178] 미로 탐색 (JAVA)
# 문제 설명 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌
spicyrisotto.tistory.com
728x90