BFS/DFS 공부

그래프 표현

• 그래프는 그림을 이용하여 표현하는 것으로 가장 자연스럽고 이해하기에 가장 쉬운 방법이다.
• 그러나 컴퓨터는 그림으로 표현된 정보를 이용할 수 없기 때문에 인접 행렬이나 인접 리스트에 의해 표현된다.

인접 행렬

• 2차원 배열로 인접 행렬을 표현한다.
• 원래 정점의 개수가 N이면 N X N 행렬로 표현한다.
• 여기서 고려할 점은 배열 크기가 N이면 인덱스는 0 ~ N-1로 표현된다.
• “정점 번호가 1번부터 N번까지” 이기 때문에 인덱스 0을 제외하고 1부터 N까지 표현하기 위해서 배열 크기를 N+1로 한다.
• 정점이 양방향으로 연결되었다면 각각 1로 저장한다.

코드로 표현하면 다음과 같다

int map[5][5]; // 그래프 표현
int visited[5]; // 현재 방문한 정점 체크

// 간선 연결
for (int i = 0; i < M; i++) {
    cin >> a >> b;
    map[a][b] = 1;
    map[b][a] = 1;
}

인접 리스트

• 베열 Vector를 사용해서 인접 리스트를 표현한다.
• 여기서 고려할 점은 배열 크기가 N이면 인덱스는 0 ~ N-1로 표현된다.
• “정점 번호가 1번부터 N번까지” 이기 때문에 인덱스 0을 제외하고 1부터 N까지 표현하기 위해서 배열 크기를 N+1로 한다.
• 정점이 양방향으로 연결되었다면 각각 1로 저장한다.

코드로 표현하면 다음과 같다

vector<int> map[5]; // 인접 리스트로 그래프 표현
int visited[5]; // 현재 방문한 정점

// 간선 연결
for (int i = 0; i < M; i++) {
    cin >> v1 >> v2;
    map[v1].push_back(v2);
    map[v2].push_back(v1);
}

BFS/DFS

BFS

void BFS(int v) {
    queue<int> q; // BFS용 큐 생성
    visited[next] = 1; // 방문기록
    q.push(V); // 시작노드 큐에 넣음

    while (!q.empty()) {
        int next = q.front(); // 큐 맨 앞에 값을 방문
        q.pop(); // 큐에서 제거

        for(int i=1; i<=N; i++) {
            if (map[next][i] == 1 && visited[i] == 0) {
                visited[i] = 1; // 방문기록
                q.push(i); // 큐에 넣음
            }
        }
    }
}

1. 시작 정점 v를 결정한다.
2. 시작 정점을 방문기록한다.
3. 시작 정점을 큐에 넣는다.
4. 큐가 공백인지 검사하고 공백이 될떄까지 반복한다.
5. 큐 맨 앞에 정점을 방문한다.
6. 방문한 정점은 큐에서 제거한다.
7. 1번부터 N번까지 정점를 탐색한다.
8. 현재 정점과 연결되었고 방문하지 않은 정점이 있으면 방문기록하고 그 정점을 큐에 집어 넣었는다.

DFS

void DFS(int v) {
    visited[v] = 1; // 방문기록

    // 그래프 탐색 방법
    for (int i = 1; i <= N; i++) {
        // 현재 정점과 연결되어있고 방문되지 않았으면 발동
        if (map[v][i] == 1 && visited[i] == 0)
            DFS(i);
        }
}

1. 시작 정점 v를 결정한다.
2. 현재 방문한 정점을 기록한다.
3. 1번부터 N번까지 정점을 탐색한다.
4. 현재 정점과 연결되었고 방문하지 않은 정점이 있으면 그 정점으로 재귀호출한다.

BFS/DFS 생각할 요소

멀리 떨어진 구역 탐색 방법

• 이중 for문을 돌아서 탐색을 한다.
• 갈 수 없는 길이거나 중복 탐색을 막기 위해서 조건을 걸어야 한다.
  • 즉, 갈 수 있는 길이거나 방문하지 않는 길이면 탐색을 하게 한다.

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
      	if (map[i][j] == 1 && visited[i][j] == 0) {
              num++;
              bfs(i, j);
              v.push_back(result);
      }
      }
    }
    

허용 가능한 탐색 범위

• 2차원 배열의 구조를 이해하면 간단하게 생각할 수 있다.
• 2차원 배열을 A[n][m]인 경우 배열 구조가 A[0][0] ~ A[n-1][m-1]이기 때문에 범위는 0<=X<N && 0<=Y<M이다.

  if ((next_x >= 0 && next_x < N)&&(next_y>=0&&next_y<N))
  

• 문제에서 만약 (1,1)부터 (N,M)까지 탐색하라고 명시한다면 A[n+1][M+1]로 선언한다.
  • 배열 구조가 A[0][0] ~ A[n+1][M+1]이기 때문에 범위는 1<=X<=N && 1<=Y<=M이다.

    if ((next_x >=1  && next_x <= N)&&(next_y>=1&&next_y<=N))
    

시작 정점 방문 시 초기화

• 지나갈 수 있는 길이고 방문하지 않은 길을 BFS 탐색 좌표로 한다.
• 시작 정점을 방문할 때 문제에서 필요한 내용을 초기화하는 것을 잊으면 안된다.

인접한 영역에 영향을 주는 문제의 경우

• 백준의 토마토와 연구소 같이 길을 탐색하는 것이 아니라 인접한 영역에 영향을 주는 문제들이 있다.
• 단지번호붙이기 같은 연결된 선이 아니라 여러 점인 경우는 이중 for문을 사용할 때 시간 초과가 발생할 수 있다.
• 그래서 지도에서 해당 점을 찾기 위해 BFS하는 것이 아니라 해당 점을 미리 찾아서 BFS하는 것이다.

// 탐색할 바이러스 큐에 삽입
for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		if (map[i][j] == 2) {
			q.push(make_pair(i, j));
		}
	}
}

참조

• C로 배우는 쉬운 자료구조 4탄, 이지영, 한빛아카데미, 2022
• 4차 산업혁명 시대의 이산수학, 김대수, 생능출판, 2019
• [자료구조] C++ vector로 그래프 구현하기 (포인터 없이 인접리스트 구현)
• [C++] 백준 2606 - 바이러스
• [백준][Python] 1260번 DFS와 BFS(DFS/BFS 기본 구현 자세히)
• [백준] 1260 DFS와 BFS C++ (BFS/DFS)