[Java] 그래프 표현(인접행렬, 인접리스트, 간선배열)및 탐색(DFS, BFS) | 백준 1260 풀이

1. 인접행렬

- |V| x |V| 크기의 2차원 배열 이용해 간선유무를 값으로 저장한다. (정점끼리 연결이면 1, 아니면 0)

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);

	int V = sc.nextInt(); // 정점의 개수를 입력받는다 시작정점이 0번인지 1번인지
	int E = sc.nextInt();
	int[][] adjArr = new int[V + 1][V + 1]; // 정점이 1번부터 시작할 때 인덱스를 조정하지 않아도 돼서 유리함

	// 간선 입력
	for (int i = 0; i < E; i++) {
		int start = sc.nextInt();
		int end = sc.nextInt();
		adjArr[start][end] = 1; // 유향 그래프라면 이것만 작성
		adjArr[end][start] = 1; // 무향 그래프일 경우 이도 같이 작성해줘야 한다
	}
}

단점 : 간선의 수 작으면 배열로 선언한 공간들이 낭비된다
→ 이에 따라, 인접리스트의 등장

 

 

 

2. 인접리스트

- 연결리스트들의 배열

- 각 정점에 대한 인접정점들을 순차적으로 표현

List<Integer>[] adjList = new ArrayList[V + 1];
for (int i = 0; i < V + 1; i++) {
	adjList[i] = new ArrayList<>();
}

// 간선 입력
for (int i = 0; i < E; i++) {
	int start = sc.nextInt();
	int end = sc.nextInt();

	adjList[start].add(end);
	adjList[end].add(start);
}

연결리스트 단점: 정점0-정점1의 연결 확인하려면 탐색해야 함. 바로 알 수X

 

	인접행렬	인접리스트
장점	조회 빠름(2개의 정점 연결유무 바로 확인)	메모리 낭비X
단점	메모리초과 위험성 간선의 수 적을 경우 메모리 낭비	시간초과 위험성 조회가 느림

 

 

3. 간선배열

- 간선정보를 배열에 저장

- 간선 표현하는 두 정점의 정보를 배열, 객체로 저장

	static class Edge {
		int start, end;
		public Edge(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();

		// 2가지 방법으로 사용 가능
		Edge[] edges = new Edge[E];
		List<Edge> edges2 = new ArrayList<>();

		for (int i = 0; i < E; i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			edges[i] = new Edge(start, end);
		}
	}

 

 

 

 

1. DFS (깊이 우선 탐색)

- 트리와 그래프 탐색의 차이점: 그래프는 트리와 달리, 서로 부모-자식 관계가 아니므로 무한으로 사이클을 돌 가능성이 존재한다.

- 따라서, visited[V]를 통하여 정점 방문 시 방문처리를 해주어야 한다. 빌리지 손가락

static void dfs(int V) {
	visited[V] = true; // 방문처리
	System.out.println(V);

	for (int i = 0; i < N; i++) { // 인접행렬을 순회하면서
		if (!visited[i] && adj[V][i] == 1) // 방문하지 않았고, 그래프가 연결되어 있다면
			dfs(i);
	}
}

(1) 현재 정점은 방문처리 해주고

(2) 현재 정점과 인접한 정점들에 대해서 방문하지 않았다면 DFS 재귀 호출 (재귀를 사용하면 자동으로 시스템스택을 사용한다.)

 

 

 

 

2. BFS(너비 우선 탐색) 

- 인접노드들부터 차례대로 방문하므로 시작정점과 끝 정점 주어졌을 때 최단길이 구할 수 있다. (DFS는 별도의 장치가 필요하나, BFS는 그냥 돌리면 최단경로 찾을 수 있음.) 와이파이

- 같은 레벨끼리 탐색

Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[N];

// 시작정점을 넣고 시작
queue.add(0);
visited[0] = true;

while (!queue.isEmpty()) { // 큐가 빌 때까지
	int curr = queue.poll(); // 정점을 꺼내고
	System.out.println(curr + " -> ");

	// 나와 연결된 자식노드들을 큐에 추가
	for (int i = 0; i < adj.length; i++) {
		if (!visited[i] && adj[curr][i] == 1) { // 방문하지 않았고 && curr와 i가 인접하면
			queue.add(i);
			visited[i] = true; // 방문처리
		}
	}
}

 

 

 

 

---

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

public class Main {
	static int n, m, v; // 정점 개수, 간선 개수, 탐색시작 정점
	static int[][] adjArr;
	static boolean[] visited;
	static Queue<Integer> q;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		v = sc.nextInt();

		adjArr = new int[n][n];
		visited = new boolean[n];

		for (int i = 1; i < m + 1; i++) {
			int st = sc.nextInt() - 1; // 시작정점 0번부터 시작하도록 구현
			int ed = sc.nextInt() - 1;

			adjArr[st][ed] = 1;
			adjArr[ed][st] = 1;
		}

		dfs(v - 1);
		System.out.println();
		bfs(v - 1);

	}

	private static void dfs(int v) {
		visited[v] = true;

		System.out.print(v + 1 + " ");

		for (int i = 0; i < adjArr.length; i++) {
			if (!visited[i] && adjArr[v][i] == 1) {
				dfs(i);
			}
		}
	}

	private static void bfs(int v) {
		visited = new boolean[n];
		q = new LinkedList<>();
		q.add(v);
		visited[v] = true;

		while (!q.isEmpty()) {
			int curr = q.poll();
			System.out.print(curr + 1 + " ");

			for (int i = 0; i < adjArr.length; i++) {
				if (!visited[i] && adjArr[curr][i] == 1) {
					q.add(i);
					visited[i] = true;
				}
			}
		}
	}
}