[코딩 테스트 준비 - 기초] 9. 그래프 - DFS & BFS

1. 그래프

• G = ( V , E ) : 그래프는 정점(vertex)과 간선(edge)들의 집합이다.
• 방향 있는 그래프(유향 그래프) u -> v
• 방향 없는 그래프(무향 그래프) u - v

 

2. 그래프의 표현

다음 그래프를 표현하는 방법 세 가지를 알아보자.

그래프 예시

1) 인접 행렬(Adjacency Matrix)

• 2차원 배열로 구현
• 장점: 임의의 두 정점 사이에 간선 존재 여부를 O(1)에 판단할 수 있다.
• 단점: 공간 낭비가 심하다 (O(V^2))
• 효율성: O(V)

2) 인접 리스트(Adjacency List)

• 포인터 배열(vector)로 구현
• 장점: 공간을 효율적으로 쓴다. (O(E))
• 효율성: O(정점의 차수)

3) 간선 리스트(Edge List)

• vector를 사용할 수 없는 환경에서 Linked List 구현에 자신이 없을 때 사용한다.
• 배열로 구현하며, 간선을 모두 저장하고 있다. 
• (잘 사용하지 않음)

 

3. 그래프의 탐색

그래프 탐색의 목적은 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 것이다.

탐색 방식으로 DFS와 BFS 두 가지가 있다.

 

1) DFS

• 깊이 우선 탐색
• 스택 이용 (재귀 호출 이용)
• 한 정점에서 갈 수 있는 만큼 최대한 많이 가고, 더 이상 갈 수 없으면 이전 정점으로 돌아간다.
• 함수를 호출하는 것이 정점을 방문했다는 의미이다.

 

인접 행렬 구현 (상하좌우 탐색 경우)

char a[26][26];
bool visited[26][26];

//오른, 아래, 왼, 위
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void dfs(int x, int y){
	visited[x][y] = true;
	//(x, y)방문할 때 필요한 작업 처리
    
	//인접 정점 체크
	for(int i=0; i<4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];

		if(nx < 0 || nx >= n || ny < 0 || ny >= n) //경계값 제어
			continue;

		if(a[nx][ny] == '1' && !visited[nx][ny]){
			dfs(nx, ny);
		}
	}
}

 

 

인접 리스트 구현

bool visited[1001];
vector<int> v[1001];

void dfs(int cur){
	visited[cur] = true;
	//정점 cur을 방문할 때 필요한 작업 처리
	for(int i=0; i<(int)v[cur].size(); i++){
		if(!visited[v[cur][i]]){
			dfs(v[cur][i]);
			//인접 정점으로부터 backtrack할 때 필요한 작업 처리
		}
	}
	//v종료되었다고 표시
	//v에서 시작하는 dfs를 마친 후 필요한 작업 처리
}

 

2) BFS

• 너비 우선 탐색
• 큐 이용
• 한 정점에서 갈 수 있는 모든 정점을 큐에 넣고 방문 표시를 한다.
• 큐에 넣는 것이 정점을 방문했다는 의미이다.

 

인접 행렬 구현 (상하좌우 탐색 경우)

char a[26][26];
bool visited[26][26];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void bfs(int x, int y){
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;

	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;

			if(a[nx][ny] == '1' && !visited[nx][ny]){
				//정점 (nx, ny)을 방문할 때 필요한 작업 처리
				q.push(make_pair(nx, ny));
				visited[nx][ny] = true;
			}
		}
	}
}

 

 

인접 리스트 구현

bool visited[1001];
vector<int> v[1001];

void bfs(int cur){
	queue<int> q;
	q.push(cur);
	visited[cur] = true;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i=0; i<(int)v[x].size(); i++){
			if(!visited[v[x][i]]){
				//정점 v[x][i]을 방문할 때 필요한 작업 처리
				q.push(v[x][i]);
				visited[v[x][i]] = true;
			}
		}
	}
}