#6 코테준비 - BFS(Breadth First Search)

BFS(Breadth First Search)

 

한 노드에서 시작해서 인접한 노드를 먼저 탐색하는 그래프 탐색 알고리즘이다.

코테에서는 다차원 배열에서 각 칸을 방문할 때 너비 우선으로 방문하는 알고리즘이라고 생각하면 된다.

 

---

C++ STL - pair

 BFS 문제를 풀때는 Queue와 pair를 사용하기 때문에 pair를 알아두면 좋다.

 

int main()
{
	pair<int, int> P; 

	P = make_pair(3, 5); 

	cout << P.first << ' ' << P.second<<'\n';

	P = { 2,7 };

	cout << P.first << ' ' << P.second << '\n';

	return 0;
}

#include<utility> 를 해주어야 하고, pair<자료형,자료형> 변수명 으로 선언한다.

값을 넣을땐 make_pair를 통해서 넣어도 되고, 간단하게 { }를 써서 넣어도 된다.

pair 안에 들어가있는 값은 변수명.first / 변수명.second로 접근 가능하다. 

 

---

BFS의 과정

1. 시작할 위치에 방문했다는 표시를 남기고 해당 칸을 큐에 넣음

2. 큐가 비어있지 않을때까지만 while문을 시작함.

3. 큐의 front를 pop하고 상하좌우를 살핌

4. 상하좌우를 탐색하며 방문한 칸에 표시를 남기고 큐에넣음

5. 큐가 비어있지 않다면 1번으로 돌아가 반복

 

글로만 보면 이해가 안가기 때문에 코드를 보고 이해하는 과정이 필요하다.

 

---

문제 풀어보기 - 1926번: 그림 (acmicpc.net)

1926번: 그림

2차원 배열의 도화지를 탐색하며 그림이 몇개인지, 그림중 가장 넓은 그림의 넓이를 출력하는 문제다.

 

#include <iostream>
#include<queue>
#include<utility>
using namespace std;

int board[502][502]; // 도화지 배열
bool vis[502][502]; // 방문을 했는지 기록할 배열
int dx[4] = {1,0,-1,0}; //상하좌우를 살피기위한 배열
int dy[4] = {0,1,0,-1}; //상하좌우를 살피기위한 배열

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	int max = 0; //가장 큰 그림넓이
	int cnt = 0; //그림 카운트

	cin >> n >> m;

	//도화지의 크기 입력받기
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];

	//2중 for문으로 여러 그림을 검사
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
		{
        	//그림이 아니거나 방문한곳이면 continue
			if (board[i][j] == 0 || vis[i][j]) continue;

			cnt++; //그림 카운트 증가
			queue<pair<int, int>> Q;
			vis[i][j] = 1;//방문했음을 기록
			Q.push({ i,j }); //그림이 시작하는 위치를 큐에 넣어줌
			int width = 0; // 그림의 넓이를 저장

			while (!Q.empty())
			{
				width++; //Q를 pop할때마다 넓이 증가시킴
				pair<int, int> cur = Q.front(); // 현재 탐색하는 좌표 저장
				Q.pop(); 
                
                //for문을 돌며 상하좌우 살핌
				for (int dir = 0; dir < 4; dir++)
				{
					int x = cur.first + dx[dir];
					int y = cur.second + dy[dir];

					//도화지 배열의 인덱스를 넘었는지 확인
					if (x < 0 || x >= n || y < 0 || y >= m) continue;
					//방문을 했거나 빨간칸인지 확인
					if (vis[x][y] || board[x][y] != 1) continue;
					
                    //위의 조건을 통과했다면 방문표시를하고 큐에 넣어줌
					vis[x][y] = 1;
					Q.push({ x,y });

				}

			}

			//큐에 더이상 원소가 없어서 while문을 빠져나오면 그림의 최대넓이 판단
			max = max >= width ? max : width;
		}
	}

	cout << cnt << '\n' << max;

	return 0;
}

 

나도 아직 코드짜기가 버거워서 주석으로 설명을 달아놨다.

다만 전역변수로 선언한 dx,dy 배열이 코드를 한결 편하게 해준다.

 

탐색을 하며 한 원소의 상하좌우를 살펴야 하는 for문을 돌릴때(47번줄) 현재 좌표를 저장해놓은 cur 변수에 dx와 dy를 각각 더해주는 과정이 있는데 , 예를 들어보면..

 

int dx[4] = {1,0,-1,0}; //상하좌우를 살피기위한 배열
int dy[4] = {0,1,0,-1}; //상하좌우를 살피기위한 배열

 

cur이 <2,3> 이라고 가정했을때 

i 가 0이면

x = cur.first+dx[0] 

y = cur.second+dy[0] 

 

x 는 2+1 =  3 / y는 3+0 = 3.

 

즉 , board[3][3]을 확인하기 때문에 cur(board[2][3])의 바로 위에 있는 칸을 탐색하는 것이다.

이런식으로 for문을 돌리면 상하좌우를 다 확인하게 된다.

 

처음이라 이해가 잘 안돼서 남의 코드를 공부하고 푼거라 내가 푼건 아니다...ㅠㅠ

---

2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

입력받은 0,0에서 배열[n][m]으로 가는 최소의 거리를 출력하는 문제다.

 

#include<iostream>
#include<queue>
#include<utility>

using namespace std;

string board[102]; //한줄로 입력받기 때문에 string 배열
int dist[102][102]; // 거리를 저장할 배열
int dx[4] = {0,0,1,-1}; //상하좌우를 살필때 도와줄 배열
int dy[4] = {1,-1,0,0}; //상하좌우를 살필때 도와줄 배열
int n, m; 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m; //미로의 크기 

	//한줄로 입력받음
	for (int i = 0; i < n; i++) cin >> board[i]; 
    
    //미로의 행을 순서대로 돌며 -1로 초기화 시켜줌
	for (int j = 0; j < n; j++) fill(dist[j], dist[j] + m, -1); 

	
	queue<pair<int, int>> Q;
	Q.push({ 0,0 }); // 큐에 0,0을 넣어주고 시작
	dist[0][0] = 0; //거리의 계산을 위해 시작점에 0을 넣어줌

	while (!Q.empty())
	{
		pair<int, int> cur = Q.front();
		Q.pop();
		
        //상하좌우 살피기
		for (int i = 0; i < 4; i++)
		{
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];
			
            //인덱스를 벗어나는지 확인
			if (x < 0 || x >= n || y < 0 || y >= m) continue;
            //못가는 길이거나 이미 탐색한 길인지 확인
			if (board[x][y] == '0' || dist[x][y] != -1) continue;
			
            //상하좌우를 살피기 때문에 cur dist에 1을 더한 값을 넣어줌
			dist[x][y] = dist[cur.first][cur.second]+1;
			Q.push({ x,y });
		}
	}
	
    //문제에서 시작점을 1,1로 여기며, 거리를 0,0부터 1로 계산하기 때문에 아래와같이 작성
	cout << dist[n - 1][m - 1]+1;

	return 0;
}

그림 문제와 비슷한 형식이지만 그림 문제는 그림이 1개가 아니기 때문에 여러곳을 탐색해야 했다면, 이 문제는 시작점에서부터 이어진 부분까지 쭉 탐색하면 되기때문에 이중 for문이 필요가 없음.

---

어떻게 돌아가는지 조금씩 이해는 되지만 문제를 계속 풀어봐야 익숙해질 것 같다.

다른 알고리즘 보다 코드 짜는 방식이 뭔가 재밌는 것 같다.