BFS, DFS

BFS 구조

BFS는 너비 우선 탐색 알고리즘으로 현재 위치에서 상하좌우로 이동합니다. 현재 그림에서는 맨 왼쪽, 맨 위의 위치에서 시작한다고 가정 하였으며 중복해서 방문하진 않으므로 화살표는 맨 오른쪽 맨 아래를 향하도록 표현하였습니다.

BFS 코드

방향 설정

int xp[4] = { 0,1,0,-1 };
int yp[4] = { 1,0,-1,0 };

이동을 나타내는 배열입니다. 반복문을 통해서 상하좌우로 이동하며 값의 순서는 임의로 해도 됩니다. 위의 코드 같은 경우에는 우하좌상 으로 이동합니다.

변수 초기화

queue<pair<int, int>> q;
q.push({ 0,0 });
visi[0][0] = 1;

q에는 현재 x, y의 위치를 담고 있습니다. 첫 시작은 0, 0이며 visi 배열은 방문 여부를 담으며 1이면 미방문 0이면 방문으로 표시하였습니다.

이동

while (!q.empty()) {
    pair<int, int> temp = q.front();
    q.pop();
    for (i = 0; i < 4; i++) {
        int nx = temp.first + xp[i];
        int ny = temp.second + yp[i];
        if (nx < 0 || nx >= tx || ny < 0 || ny >= ty)continue;
        if (visi[nx][ny] == 1)continue;
        q.push({ nx,ny });
        visi[nx][ny] = 1;
    }
}

큐에서 값을 꺼내어 위에서 설정한 방향대로 x와 y의 값에 더해서 이동합니다. 범위를 넘어서거나 이미 방문한 위치일 경우 무시하며 새로운 위치 도착 시 큐에 push 후 방문표시를 해줍니다.

DFS 구조

DFS는 깊이 우선 탐색 알고리즘으로 현재 위치에서 상하좌우 중 한 방향으로 계속 향합니다. 현재 그림에서는 맨 왼쪽, 맨 위의 위치에서 시작한다고 가정 하였으며 중복해서 방문하진 않으므로 화살표는 맨 오른쪽 맨 아래를 향하도록 표현하였습니다.

DFS 코드

초기화

while (m--) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
}

사용자 입력을 통해 노드 번호끼리 서로 연결 해줍니다.

이동

void dfs(int here) {
    for (int next : adj[here]) {
        if (visi[next])continue;
            visi[next] = 1;
        dfs(next);
    }
}

자신과 연결된 노드끼리 방문하지 않았던 노드들 하나씩 마지막 정점에 도달할때까지 순회합니다.