-
[C++] BFS(Breadth First Search) ๋๋น ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆAlgorithm & Data Structure 2022. 1. 21. 23:01๋ฐ์ํ
๋ค์ด๊ฐ๋ฉฐ
BFS๋ ์ฝ๋ฉํ ์คํธ์ ์์ฃผ ์ฌ์ฉ๋๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. Flood Fill๊ณผ ๊ฐ์ ๋ฌธ์ ๋ค์ ํด๊ฒฐํ๋ ๋ฐ ์ฌ์ฉํ ์ ์๋ค. ์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด์๋ Queue(ํ)๋ฅผ ์ฌ์ฉํ๋ค!
BFS(๋๋น ์ฐ์ ํ์) ์ด๋?
๋๋น ์ฐ์ ํ์(Breadth-first search, BFS)์ ๋งน๋ชฉ์ ํ์๋ฐฉ๋ฒ์ ํ๋๋ก ์์ ์ ์ ์ ๋ฐฉ๋ฌธํ ํ ์์ ์ ์ ์ ์ธ์ ํ ๋ชจ๋ ์ ์ ๋ค์ ์ฐ์ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ๋ฒ์ด๋ค. ๋ ์ด์ ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ด ์์ ๋๊น์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ชจ๋ ์ ์ ๋ค์ ๋ํด์๋ ๋๋น ์ฐ์ ๊ฒ์์ ์ ์ฉํ๋ค. OPEN List๋ ํ๋ฅผ ์ฌ์ฉํด์ผ๋ง ๋ ๋ฒจ ์์๋๋ก ์ ๊ทผ์ด ๊ฐ๋ฅํ๋ค.
- ์ํค๋ฐฑ๊ณผBFS ์๊ณ ๋ฆฌ์ฆ
์๋์ ์ฌ์ง๋ค์ ๋ณด๊ณ BFS๋ฅผ ์ดํดํด๋ณด์.
์์ ์ง์ ์ด 1์ด๋ผ๊ณ ํ์. ๊ทธ๋ฌ๋ฉด 1์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํด๋น ์นธ์ ํ์ ๋ฃ๋๋ค. ๊ทธ๋ฆฌ๊ณ ํ๊ฐ ๋น ๋๊น์ง ํ์ front๋ฅผ ๋นผ๊ณ ๋บ ์ขํ์ ์ฃผ๋ณ(์ํ์ข์ฐ)์ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด ํ์ ๋ฃ์ด์ค๋ค.
ํ์ front์ธ 1์ ์ญ์ ํ๊ณ 1์ ์ฃผ๋ณ์ธ 2์ 3์ ํ์ํ์ผ๋ฏ๋ก ์ด ์นธ๋ค์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํ์ ๋ฃ๋๋ค.
ํ์ front์ธ 2๋ฅผ ์ญ์ ํ๊ณ 2์ ์ฃผ๋ณ์ธ 4์ 5๋ฅผ ํ์ํ์ผ๋ฏ๋ก ์ด ์นธ๋ค์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํ์ ๋ฃ๋๋ค.
ํ์ front์ธ 3์ ์ญ์ ํ๊ณ 3์ ์ฃผ๋ณ์ธ 6๊ณผ 7์ ํ์ํ์ผ๋ฏ๋ก ์ด ์นธ๋ค์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํ์ ๋ฃ๋๋ค.
ํ์ front์ธ 4๋ฅผ ์ญ์ ํ๊ณ 4์ ์ฃผ๋ณ์ธ 8์ ํ์ํ์ผ๋ฏ๋ก ์ด ์นธ์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํ์ ๋ฃ๋๋ค.
ํ์ front์ธ 5๋ฅผ ์ญ์ ํ๊ณ 5์ ์ฃผ๋ณ์ธ 9๋ฅผ ํ์ํ์ผ๋ฏ๋ก ์ด ์นธ์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํ์ ๋ฃ๋๋ค.
๋๋จธ์ง๋ค๋ ๋๊ฐ์ ๊ณผ์ ์ผ๋ก ํ์ front๋ฅผ ํ์ธํ๋ ๋ฑ์ ๊ณผ์ ์ ํ๋๋ฐ ํด๋น ์ฃผ๋ณ์ ์ขํ๋ค์ ๋ชจ๋ ๋ฐฉ๋ฌธํ์ผ๋ฏ๋ก ํ์์ ์ญ์ ํ๋ค.
BFS ๋ฌธ์ ํด๊ฒฐ
- ์์ํ๋ ์นธ์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ํ๊ณ ํ์ ๋ฃ๋๋ค.
- ํ์ front์ ์๋ ์์๋ฅผ ๊บผ๋ด์ด(pop) ๊ทธ ์์์ ์ฃผ๋ณ(์ํ์ข์ฐ)์ ํ์ํ๋ค. ๋ง์ฝ ํด๋น ์นธ์ ์ด์ ์ ๋ฐฉ๋ฌธํ๋ค๋ฉด ๋์ด๊ฐ๊ณ , ์ฒ์์ผ๋ก ๋ฐฉ๋ฌธํ๋ค๋ฉด ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํด๋น ์นธ์ ํ์ ๋ฃ๋๋ค.
- ํ๊ฐ ๋น ๋๊น์ง ๊ณ์ํด์ 2๋ฒ์ ๋ฐ๋ณตํ๋ค.
* ๋ชจ๋ ์นธ์ ํ์ 1๋ฒ์ฉ ๋ค์ด๊ฐ๋๊น BFS ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ ์นธ์ด n๊ฐ๋ผ๋ฉด O(n)์ด๋ค. ๋ง์ฝ์ ํ์ด r๊ฐ, ์ด์ด c๊ฐ๋ผ๋ฉด ์๊ฐ ๋ณต์ก๋๋ O(rc)์ด๋ค.
์๋์ ์ฝ๋๋ BFS๋ฅผ ์ดํดํ ์ ์๋ ์ฝ๋์ด๋ค.
#include <bits/stdc++.h> using namespace std; #define X first // pair์์ first ๋ฅผ ์ค์ฌ ์ฐ๊ธฐ ์ํด #define Y second // pair์์ second๋ฅผ ์ค์ฌ์ฐ๊ธฐ ์ํด int board[502][502] = {{1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0} }; // 1์ด ํ๋ ์นธ, 0์ด ๋นจ๊ฐ ์นธ์ ๋์ bool vis[502][502]; // ํด๋น ์นธ์ ๋ฐฉ๋ฌธํ๋์ง์ ์ฌ๋ถ๋ฅผ ์ ์ฅ int n = 7, m = 10; // n = ํ์ ์, m = ์ด์ ์ int dx[4] = { 1, 0, -1, 0 }; // ์ํ์ข์ฐ 4๊ฐ์ ๋ฐฉํฅ์ ์๋ฏธ int dy[4] = { 0, 1, 0, -1 }; // ์ํ์ข์ฐ 4๊ฐ์ ๋ฐฉํฅ์ ์๋ฏธ int main(void) { ios::sync_with_stdio(0); cin.tie(0); queue<pair<int, int>> Q; vis[0][0] = 1; // (0, 0) ์ขํ๋ฅผ ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์ Q.push({0, 0}); // ํ์ ์์ ์ขํ(0, 0)๋ฅผ ๋ฃ๋๋ค. while (!Q.empty()) { pair<int, int> cur = Q.front(); // ์์์ ์ฃผ๋ณ์ ํ์ํ๊ธฐ ์ํด cur๋ฅผ ์ฌ์ฉํ๋ค. Q.pop(); // ํ์ front์ ์๋ ์์๋ฅผ ๊บผ๋ธ๋ค. cout << '(' << cur.X << ", " << cur.Y << ") -> "; for (int dir = 0; dir < 4; dir++) { // ์ํ์ข์ฐ ์นธ์ ํ์ํ๋ค. int nx = cur.X + dx[dir]; // nx์ dir์์ ์ ํ ๋ฐฉํฅ(์ํ์ข์ฐ)์ ์ธ์ ํ ์นธ์ ์ขํ๊ฐ ๋ค์ด๊ฐ๋ค. int ny = cur.Y + dy[dir]; // ny์ dir์์ ์ ํ ๋ฐฉํฅ(์ํ์ข์ฐ)์ ์ธ์ ํ ์นธ์ ์ขํ๊ฐ ๋ค์ด๊ฐ๋ค. if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; // ๋ฒ์๋ฅผ ๋ฒ์ด๋ ๊ฒฝ์ฐ์๋ ๋์ด๊ฐ๋ค. } if (vis[nx][ny] || board[nx][ny] != 1) { continue; // ์ด๋ฏธ ๋ฐฉ๋ฌธํ ์นธ์ด๊ฑฐ๋ ๋ฐฉ๋ฌธํ ํ์๊ฐ ์๋(๋นจ๊ฐ ์นธ)์ผ ๊ฒฝ์ฐ ๋์ด๊ฐ๋ค. } vis[nx][ny] = 1; // (nx, ny) ์ขํ๋ฅผ ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์ํ๋ค. Q.push({nx, ny}); // ํด๋น ์นธ์ ํ์ ๋ฃ๋๋ค. } } return 0; }
๋ฐ์ํ