그래프 탐색 (BFS, DFS)

선행 지식

Graph : 정점(Vertex)와 그 정점을 연결하는 간선(Edge)를 하나로 모아 놓은 자료구조

정점(Vertex) : 노드(Node) : 값이 저장되는 그래프의 각 원소

간선(Edge) : 각 정점을 이어주는 선분

사이클 : 단순 경로에서 시작 정점과 종료 정점이 동일한 경우

차수 : 그래프에서 한 정점에 인접한 정점의 수

그래프의 종류

양방향 그래프 : 그래프의 방향이 없는 그래프, (A,B)와 (B,A)가 동일

단방향 그래프 : 그래프의 방향이 있는 그래프, A→B를 <A,B>라 표시하며 <A,B> ≠ <B,A>

가중치 그래프 : 간선의 비용이나 가중치가 할당된 그래프

완전 그래프 : 모든 정점이 연결되어 있는 그래프

깊이 우선 탐색(DFS)

루트 노드(스타트 노드)에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기의 모든 자식 노드를 탐색하는 방법

구현이 간단하여 모든 정점을 방문해야 하는 경우에 사용 - Stack or 재귀로 구현

너비 우선 탐색(BFS)

루트 노드(스타트 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법

주로 노드 간의 거리를 구하거나 두 노드간의 이동 경로를 구하기 위해 사용 - Queue로 구현

그래프 유형의 dfs,bfs

vector<int> G[MAX_N];
bool visited[MAX_N];

void dfs(int cur) {
	visited[cur] = true; // 방문한 정점 체크 
	for(int nxt : G[cur]) { // 현재 노드의 자식 노드 모두 순회
		if(!visited[nxt]) { // 자식노드를 방문하지 않았다면
			dfs(nxt); // 자식 노드로 들어 감
		}
	}
}

void bfs(int st) {
	queue<int> q;
	q.push(st); // 시작 정점 큐에 삽입 
	visited[st] = true;

	while(!q.empty()) { // 큐가 비어있지 않을 때 까지
		int cur = q.front(); // 다음 노드를 가져옴
		q.pop();

		for(int nxt : G[cur]) { // 현재 노드의 자식 노드 모두 순회
			if(!visited[nxt]) { // 자식 노드를 방문하지 않았다면
				q.push(nxt); // 큐에 삽입
				visited[nxt] = true;
			}
		}
	}
	cout << '\n';
}

int main() {
	int N,M;
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int u,v;
		cin >> u >> v;
		G[u].push_back(v); // u에서 v로 가는 간선 추가
		G[v].push_back(u); // v에서 u로 가는 간선 추가
	}
	dfs(시작 정점);
	memset(visited,0,sizeof(visited));
	bfs(시작 정점);
}

인접행렬 유형의 dfs, bfs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int w,h,cnt;
int my_map[55][55],visited[55][55];
int dir[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};

void dfs(int y, int x) {
    visited[y][x] = 1;
    for(int i=0; i<8; i++) {
        int ny=y+dir[i][0], nx=x+dir[i][1];
        if(ny<0 || ny>=h || nx<0 || nx>=w) continue;
        if(!my_map[ny][nx] || visited[ny][nx]) continue;
        dfs(ny,nx);
    }
}

void bfs(int y, int x) {
    queue<pair<int,int> > q;
    q.push(make_pair(y,x));
    visited[y][x] = 1;
    while(!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        for(int i=0; i<8; i++) {
            int ny = cur.first+dir[i][0], nx = cur.second+dir[i][1];
            if(ny<0 || ny>=h || nx<0 || nx>=w) continue;
            if(!my_map[ny][nx] || visited[ny][nx]) continue;
            q.push(make_pair(ny,nx));
            visited[ny][nx] = 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while(1) {
        cin >> w >> h;
        if(!w && !h) break;
        cnt = 0;
        memset(visited,0,sizeof(visited));
        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++)
                cin >> my_map[i][j];
        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++) {
                if(!my_map[i][j] || visited[i][j]) continue;
                bfs(i,j);
                cnt++;
            }
        cout << cnt << '\n';
    }
}