Data Structure, Graph, 프로그래머스 가장먼 노드(49189)
그래프 구성요소
1. 정점(vertex / node)
: 위치를 나타낸다.
2. 간선(edge / link / branch)
: 위치간의 관계, 정점을 연결하는 선
3. 인접 정점
: 간선에 의해 직접 연결된 정점
4. G(V,E)
: 그래프는 정점과 간선의 집합이므로 G(V,E)는 그래프 자체를 의미
그래프의 종류
무방향 그래프
: 간선을 통해 양방향으로 이동할 수 있는 그래프
간선 그래프
: 간선에 방향이 존재하는 그래프
가중지 그래프
: 간전에 비용 또는 가중치가 할당되 그래프 ‘네트워크’라고도 함
연결 그래프
: 무바향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
비연결 그래프
: 무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프
인접 정점 나타내기
(인접행렬/인접리스트)
인접 리스트
- ArrayList로 구현한다
- 노드수만큼 ArrayList를 선언한다
- 간선의 정보를 이용하여 노드에 연결된 다른 노드를 넣어준다
// n: 노드개수
// int[][] edge = [[1,2], [3,4]];
List<ArrayList<Integer>> listGraph = new ArrayList<>();
// 그래프 노드별로 정보 연결할 준비.
// 0,1,2,3,4,...n까지 기본 노드들을 만든다.
for (int i = 0; i <= n; i++) {
listGraph.add(new ArrayList<Integer>());
}
// [1,2] 라면
// listGraph.get(1).add(2) // 1번노드는 2와연결
// listGraph.get(2).add(1) // 2번노드는 1과연결
for (int i = 0; i < edge.length; i++) {
listGraph.get(edge[i][0]).add(edge[i][1]);
listGraph.get(edge[i][1]).add(edge[i][0]);
}
인접 행렬
- 배열을 이용한다
- map[i][j] = 1 , i->j j->i로 이동가능함을 표현.
- 단점 : 노드수가 많아질수록 메모리를 많이 차지한다.
문제 풀이
코드
package org.programmers;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Level3_49189 {
public static void main(String[] args) {
// github 페이지 빌드가 안되서 주석처리 & 중괄호 없앰.
//int[][] edge = [7,5] [4,2] [3,6] [4,3] [3,2] [1,2] [2,3]
int n = 7;
solution(n, edge);
}
public static int solution(int n, int[][] edge) {
boolean[] visited = new boolean[n + 1];
List<ArrayList<Integer>> listGraph = new ArrayList<>();
// == 그래프 노드별로 정보 연결할 준비.
// 0,1,2,3,4,...n까지 기본 노드들을 만든다.
for (int i = 0; i <= n; i++) {
listGraph.add(new ArrayList<Integer>());
}
// == 그래프 연결
// [1,2] 라면
// listGraph.get(1).add(2) // 1번노드는 2와연결
// listGraph.get(2).add(1) // 2번노드는 1과연결
for (int i = 0; i < edge.length; i++) {
listGraph.get(edge[i][0]).add(edge[i][1]);
listGraph.get(edge[i][1]).add(edge[i][0]);
}
Queue<Integer> nextQ = new LinkedList<>();
//== 1번부터 출발
nextQ.offer(1);
visited[1] = true;
int size = 0;
while (!nextQ.isEmpty()) {
size = nextQ.size();
// while문을 한번 돈다 -> 1번 깊이 들어간다.
// 가장 멀리 있는 곳을 찾아야 하기때문에
// while을 마지막에 돌았을때 도착하는 노드들의 개수 = size를 구하면된다.
for (int i = 0; i < size; i++) {
int cur = nextQ.poll();
visited[cur] = true;
// 해당 노드와 연결된 노드중 아직 방문하지 않는 노드를 방문한다.
for (Integer node : listGraph.get(cur)) {
if (visited[node] == false) {
nextQ.offer(node); // 다음에 방문하도록 큐에 넣어준다.
visited[node] = true;
}
}
}
}
System.out.println(size);
return size;
}
}