[알고리즘]인접행렬과 인접리스트에서의 DFS,BFS

입력값으로 간선의 정보들이 주어지는 문제에서 탐색을 요구할 경우 인접행렬 또는 인접리스트로 DFS 나 BFS로 풀게 된다.(나중에 간선정보로 푸는 문제에는 최소신장트리를 구하는 크루스칼 알고리즘도 있지만, 최소신장트리가 아닌 일반적인 그래프에서는 인접행렬 또는 인접리스트로 푸는 경우가 많다)

 

인접행렬이나 인접리스트 뭐가 절대적으로 좋다라고 말할 순 없지만, 정점의 수가 엄청 많은데 간선은 없는 경우에는 인접리스트가 더 효과적일 것이고, 밀집그래프에서는 리스트는 타고타고타고 가야하니까 시간이 오래걸리므로 인접행렬이 더 나을 것이다. 문제의 정점과 간선 수를 보고 선택하면 된다.

 

 

인접행렬에서 DFS, BFS

아래처럼 간선의 0~6까지 7개의 정점이 주어지고, 8개의 간선정보가 주어졌다. 모두 탐색하는 dfs와 bfs를 짜보자.

참고로, 방향이 없는 무향그래프로 간주한다.

입력:
7
8
0 1
0 2	
1 3
1 4
2 4
3 5
4 5
5 6

그래프로 그려보면,
  0
 / \ 
1   2
|\ /
3 4
\ |
 5 
 |
 6

키 포인트:

1. 무향이라서, 입력받을 때 from이나 to나 모두 행렬에서 똑같이 대칭되도록 1로 표현해줌. (15번라인)

2. bfs에서는 항상 그랬듯이 똑같은 패턴임. Queue만들고 처음에 시작점 넣어주기. 단, Queue에 추가하는 조건인 visited[j] && adjMatrix[current][j]!=0 은 좀 생각해보면 자연스럽게 떠오를 것임.

3. dfs도 간단하다. 단, dfs(adjMatrix, visited, j);에서 인자 j 로 하나씩 연결된 애들 다 돌아니도록 해주는 것임.

public class AdjMatrixTest {
	
	static int N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();// 정점 수
		int C = sc.nextInt();// 간선 수
		
		int[][] adjMatrix = new int[N][N];//정점수 크기로 생성
		
		for(int i=0; i<C; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			//무향이므로 간선 하나로 양방향 처리
			adjMatrix[from][to] = adjMatrix[to][from] = 1;
		}

//		bfs(adjMatrix, 0);
		dfs(adjMatrix,new boolean[N],0);
	}
	public static void bfs(int[][] adjMatrix, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		queue.offer(start);
		visited[start] = true; //큐에 들어갈때 방문체크함!!
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println(current);
			
			//current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
			for(int j=0; j<N; j++) {
				if(!visited[j] && adjMatrix[current][j]!=0) {
					queue.offer(j);
					visited[j] = true;
				}
			}
		}
	}
	
	public static void dfs(int[][] adjMatrix, boolean[] visited, int current) {
		visited[current] = true;
		System.out.println(current);
		
		//current 정점의 인접정점 처리(단, 방문하지 않은 정점만)
		for(int j=0; j<N; j++) {
			if(!visited[j] 
					&& adjMatrix[current][j]!=0) {
				dfs(adjMatrix, visited, j);
			}
		}
		
	}

}

 

 

인접리스트에서의 dfs, bfs

이게 좀 더 흥미로움. 물론 아주 살짝 까다롭지만 별거아님.

입력값은 위랑 동일.

bfs에서 노드를 직접 만드는데, 노드가 다 연결되어있다고 생각하지마삼. 그냥 Node[]가 있는데, 0번째 원소는 0번 정점과 연결되어있는 모든 정점들을 걍 모아놓은 거임. ㄹㅇ 단순하게, 0번 정점에 11번,30번,3번,8번 정점이 바로 인접해있다면, nodeList[0]은 8번 vertex를 가지고 있는 Node를 가리키고, 얘의 링크는 또 3번 vertex 노드를 가리키고,....이렇게 걍 nodeList[0]에다가 묶어놓은것임. 이때 입력들어오는 순서는 안중요하지 어차피 걍 nodeList[0]에 묶여있다고 표현만 해주면 되니까. 단, 30.31번라인에서 저렇게 순서가 있는 것처럼 한건 걍 늦게 넣는걸 맨 앞에 넣는게 단순해서 그런것임.

 

키포인트:

1. ArrayList써도 되지만, 걍 Node 직접 만들었음(이게 더 빠름. 근데 별로 어렵지도 않다.). 걍 vertex랑 link만 넣어주면 끝

2. Node[]를 만들고, 그 안에 넣어주는데, 30번,31번 라인 잘 이해하삼. 순서가 거꾸로 움직이는거임. 

3. 역시나 bfs 함수 형태는 똑같. Queue만들고 첫 시작점 넣어주고, while안에서 poll해서 하나씩 꺼내주면서 인접한애들을 Queue에 넣어주면 된다.

4. 인접한 애들 확인하는 코드가 매우 재밌음. 54번째 줄 잘 보삼.

5. dfs도 간단한다. for문안에 노드 하나씩 늘어나는것도 흥미로우니 잘보삼. 다음 dfs로 넘길때 temp.vertex로 넘기는 것도.

public class AdjListTest {
	
	static class Node{
		int vertex;//정점번호
		Node link;
		
		public Node(int vertex, Node link) {
			this.vertex = vertex;
			this.link = link;
		}

		@Override
		public String toString() {
			return "Node [vertex=" + vertex + ", link=" + link + "]";
		}
	}
	
	static int N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();// 정점 수
		int C = sc.nextInt();// 간선 수
				
		Node[] adjList = new Node[N];//정점수 크기만큼 노드 생성
		
		for(int i=0; i<C; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			//맨 앞에다가 추가하는 거임. 현재 무향 그래프니까 to에도 넣어줌.
			adjList[from] = new Node(to,adjList[from]);
			adjList[to] = new Node(from,adjList[to]);
		}
		
		for(Node head: adjList) {
			System.out.println(head);
		}
		System.out.println("-------------------");
		bfs(adjList,0);
//		dfs(adjList, new boolean[N],0);
	}
	
	public static void bfs(Node[] adjList, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		queue.offer(start);
		visited[start] = true; //큐에 들어갈때 방문체크함!!
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.println(current);
			
			//current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
			for(Node temp = adjList[current]; temp!=null; temp = temp.link) {
				if(!visited[temp.vertex]) {
					queue.offer(temp.vertex);
					visited[temp.vertex] = true;
				}
			}
		}
	}
	
	public static void dfs(Node[] adjList, boolean[] visited, int current) {
		visited[current] = true;
		System.out.println(current);
		
		//current 정점의 인접정점 처리(단, 방문하지 않은 정점만)
		for(Node temp = adjList[current]; temp!=null; temp = temp.link) {
			if(!visited[temp.vertex]) {
				dfs(adjList, visited, temp.vertex);
			}
		}
	}
}

 

 

 

관련문제

복습하기 좋은 문제는 백준의 1260번이다.

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

1260번: DFS와 BFS

풀때는 Node를 만들기가 부담스러워서 걍 인접행렬 방식으로만 풀었는데, 문제를 다시 보니까 인접행렬로 푸는게 더 효율적이겠다라는 생각이 든다. 나중에 Node만들어서 다시 해보자.

package ws0221;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ1260_DFS와BFS {

	static int N, M, V;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		V = sc.nextInt();
		
		int[][] mat = new int[N+1][N+1];
		
		for(int i=0; i<M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			mat[from][to] = mat[to][from] = 1;
		}
		
		dfs(mat, new boolean[N+1], V);
		sb.setLength(sb.length()-1);
		sb.append("\n");
//		System.out.println(sb);
		bfs(mat, V);
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}
	
	public static void bfs(int[][] adjMatrix, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N+1];
		
		queue.offer(start);
		visited[start] = true; //큐에 들어갈때 방문체크함!!
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
//			System.out.println(current);
			sb.append(current).append(" ");
			
			//current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
			for(int j=1; j<N+1; j++) {
				if(!visited[j] && adjMatrix[current][j]!=0) {
					queue.offer(j);
					visited[j] = true;
				}
			}
		}
	}

	static StringBuilder sb = new StringBuilder();
	public static void dfs(int[][] adjMatrix, boolean[] visited, int current) {
		visited[current] = true;
		
		sb.append(current).append(" ");
		
		//current 정점의 인접정점 처리(단, 방문하지 않은 정점만)
		for(int j=1; j<N+1; j++) {
			if(!visited[j] && adjMatrix[current][j]!=0) {
				dfs(adjMatrix, visited, j);
			}
		}	
	}
	
	
}

 

 

다음문제는 SWEA의 1238번 contact 문제이다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD 

SW Expert Academy

그림만 보면 다음과 같다. 가장 나중에 연락을 받게 되는 사람 중 번호가 가장 큰 사람을 구하는 거다.

이 문제는 배열이 행렬을 만들어도 어차피 수 제한이 100까지라 괜찮을 거 같아 인접행렬로 풀었다. 나중엔 노드 만들어서 인접리스트로 함 해보자.

특히 속을 좀 썩인 부분은 55번째 줄임. visited배열을 항상 boolean으로만 하다보니 몇번 방문했는지 어케 체크할지 골치가 아팠는데, int로 만들어서 큐에 넣을때 기존의 visit[current]+1만큼을 visited[i]에 넣어주면 되는 것이었다..ㅠㅠ

package ws0221;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA1238_contact {

	static int N, V;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;
		StringBuilder sb = new StringBuilder();
		
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());//받는 데이터 수
			V = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			
			int[][] mat = new int[101][101];//입력값 최댓값이 100이라서 배열로 만들어줌.
			for(int i=0; i<N/2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());		
				mat[from][to] = 1;
			}
			
			
			int ans = bfs(mat,V);
			int ans2 = ans;
			sb.append("#").append(tc).append(" ").append(ans2).append("\n");
		}
		System.out.print(sb.toString());
	}
	
	static int bfs(int[][] mat, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int[] visited = new int[101]; //체크배열을 boolean으로 하지 않고 int로함. 몇번째 방문한 것인지 체크하기 위함임.
		
		queue.offer(start);
		visited[start] = 1;
		
		int max = 0;
		int ans = 0;
		
		while(!queue.isEmpty()){
			int current = queue.poll();
			
			for(int i=1; i<101; i++) {
				if(visited[i]==0 && mat[current][i]!=0) {
					queue.offer(i);
					visited[i] = visited[current]+1; //다음 방문차례는 현재방문차례 다음이므로.
				}
			}
			max = visited[current];
		}
		
		for(int i=1; i<101; i++) {
			if(max == visited[i]) { //같은 방문차례가 있다면, 더 큰 값으로.
				ans = ans > i ? ans : i;
			}
		}
		return ans;
	}
}