알고리즘/알고리즘 관련 메모장

BFS , DFS 알고리즘 - 예제풀이

잡담연구소 2020. 12. 9. 20:42

BFS, DFS에 대해서는 이전 알고리즘 스터디에서 다뤘던 주제라서  안다. 

BFS는 너비우선탐색이고 , 큐를 사용하는 방식이고 DFS는 깊이우선탐색에 스택을 사용한다 이정도??

근데 이거만 안다고 해서 문제가 풀리지는 않더라,,,,ㅜㅜ

개념 공부하고 관련 예제 풀어보고 알고리즘 공부할때마다 느끼는 건데 수능수학 공부하는 거 같다. 

아래 블로그에서 기본 DFS,BFS에 해당하는 1-4 번 네가지 문제를 풀어보자. 

huiyu.tistory.com/entry/DFSBFS-%EC%88%99%EB%8B%AC%EC%9D%84-%EC%9C%84%ED%95%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%EA%B8%B0%EB%B3%B8%EC%9D%91%EC%9A%A9

 

백준 2606번 바이러스 (www.acmicpc.net/problem/2606)

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
using namespace std;

vector<vector<int>> computers;
vector<bool>visited;
int n;

int bfs(int x){
	queue<int>que;
	que.push(x);
	int num, cnt=0;
	while (!que.empty()) {
		num = que.front();
		que.pop();
		if (!visited[num]) {
			visited[num] = true;
			cnt++;
			for (int i = 0; i < computers[num].size(); i++) que.push(computers[num][i]);
		}
	}
	return cnt;
}

int main() {
	int edges;
	cin >> n >> edges;

	//visited 초기화
	computers.resize(n + 1);
	visited.resize(n + 1);

	//computers 그래프 초기화
	for (int i = 0; i < edges; i++) {
		int a, b;
		cin >> a >> b;
		computers[a].push_back(b);
		computers[b].push_back(a);
	}
	cout << bfs(1)-1 << endl;
}

 

내 최애 유니온파인드도 가능할 거 같아서 해봄

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
using namespace std;

vector<int>parent;
int n;

int getparents(int x) {
	if (parent[x] == x) return x;
	return parent[x] = getparents(parent[x]);
}

void unionparents(int x, int y) {
	x = getparents(x);
	y = getparents(y);
	if (x > y) parent[x] = y;
	else parent[y] = x;
}

bool find(int x, int y) {
	x = getparents(x);
	y = getparents(y);
	if (x == y) return true;
	return false;
}

int main() {
	int edges;
	cin >> n >> edges;
	parent.resize(n + 1);

	for (int i = 1; i <= n; i++) parent[i] = i;
	
	for (int i = 0; i < edges; i++) {
		int a, b;
		cin >> a >> b;
		unionparents(a, b);
	}
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (find(1, i)) cnt++;
	}
	cout << cnt;
}

백준 2667번 단지번호붙이기(www.acmicpc.net/problem/2667)

DFS 버전 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
using namespace std;

int home[25][25];
vector<int>house_number;

int n, cnt;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void dfs(int x, int y ) {
	if (x > -1 && x<n && y>-1 && y < n) {
		if (home[x][y] == 1) {
			home[x][y] = 0;
			cnt++;
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				dfs(nx,ny);
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i< n; i++) {
		for (int j = 0; j < n; j++) scanf("%1d", &home[i][j]);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cnt = 0;
			dfs(i, j);
			if (cnt != 0) house_number.push_back(cnt);
		}
	}
	sort(house_number.begin(), house_number.end());
	cout << house_number.size() << endl;
	for (int i = 0; i < house_number.size() ; i++) cout << house_number[i]<<endl;
}

BFS 버전 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
using namespace std;

int home[25][25];
vector<int>house_number;

int n, cnt;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void bfs(int i, int j) {
	queue<pair<int, int>>que;
	que.push({ i,j });
	while (!que.empty()) {
		int x = que.front().first;
		int y = que.front().second;
		que.pop();
		if (x > -1 && x<n && y>-1 && y < n) {
			if (home[x][y] == 1) {
				home[x][y] = 0;
				cnt++;
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					que.push({ nx, ny });
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i< n; i++) {
		for (int j = 0; j < n; j++) scanf("%1d", &home[i][j]);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cnt = 0;
			bfs(i, j);
			if (cnt != 0) house_number.push_back(cnt);
		}
	}
	sort(house_number.begin(), house_number.end());
	cout << house_number.size() << endl;
	for (int i = 0; i < house_number.size() ; i++) cout << house_number[i]<<endl;
}

 

백준 2589번 보물섬(www.acmicpc.net/problem/2589)

 

 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
using namespace std;

vector<vector<int>>map;
queue<pair<int, int>> que;
int n, m , cnt , max = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int bfs(int first_x, int first_y) {
	vector<vector<int>>visited;
	visited.resize(n, vector<int>(m, 0));
	que.push({ first_x, first_y });
	visited[first_x][first_y] = 1;
	int max_num = 0;
	while (!que.empty()) {
		int x = que.front().first;
		int y = que.front().second;
		que.pop();
		cnt++;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx > -1 && nx < n && ny >-1 && ny < m) {
				if ((!visited[nx][ny]) && (map[nx][ny])) {
					visited[nx][ny] = visited[x][y] + 1;
					que.push({ nx,ny });
					if (visited[nx][ny] > max_num) max_num = visited[nx][ny];
				}
			}
		}
	}
	return max_num;
}

int main() {
	cin >> n >> m;
	map.resize(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < m; j++) {
			char land = str[j];
			if (land == 'W') map[i][j] = 0;
			else map[i][j] = 1;
		}
	}
	int max_path = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1) {
				int path = bfs(i, j);
				if (path > max_path) max_path = path;
			}
		}
	}
	printf("%d", max_path-1);
}

 

로직이 맞았다고 생각하는데 자꾸 내가 원하는 답이 나오지 않아서 백준에 질문을 했다. 

www.acmicpc.net/board/view/60143#post

resize(n, T)는 현재 벡터의 크기가 n보다 작을 때 늘어나는 공간을 T로 채워 주는 역할을 합니다.
따라서 17번째 줄은 bfs가 처음 호출될 때 단 한 번만 초기화를 하고, 그 뒤로는 아무 일도 하지 않습니다

resize(n,0) 을 해주면 매번 bfs가 실행될때마다 초기화가 되는 줄 알았는데 그게 아니었다 ㅜㅜㅜ 

 

백준 토마토 7576번 (www.acmicpc.net/problem/7576)

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
using namespace std;

int tomato[1005][1005];
int visited[1005][1005];
queue<pair<int, int>>que;

int n, m;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int bfs() {
	int max_day = 1;
	while (!que.empty()) {
		int x = que.front().first;
		int y = que.front().second;
		que.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx > m - 1 || ny <0 || ny > n - 1 || visited[nx][ny] || tomato[nx][ny]) continue;
			que.push({ nx,ny });
			visited[nx][ny] = visited[x][y] + 1;
			if (max_day < visited[nx][ny]) max_day = visited[nx][ny];
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j] && !tomato[i][j]) return 0;
		}
	}
	return max_day;
}

int main() {
	cin >> n >> m; //열, 행
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tomato[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (tomato[i][j] == 1) {
				que.push({ i,j });
				visited[i][j] = 1;
			}
		}
	}
	if (que.empty()) cout << -1;
	else {
		int max_day = bfs();
		cout << max_day - 1;
	}
}

토마토가 있는 좌표를 큐에 모두 넣어주고 이 좌표들에 대해서 모두 visited = 1 로 체크를 해준다. 

그 후 좌표들을 빼서 상,하,좌,우 다음 칸으로 넘어갈떄마다 visited를 하나씩 추가해주었다. 

bfs를 다 돌았을 때, 아직도 visited 체크가 안됐으면서 tomato 가 0인 곳이 존재한다면 -1을 반환

 

효율적인 코드인지는 모르겠지만 자신감이 아주 살짝 생겼다.

이제 알고리즘 숙제하러가보겠다 뿅-😎

'알고리즘 > 알고리즘 관련 메모장' 카테고리의 다른 글

DFS로 순열 및 조합 구현  (0) 2020.12.17
C++ 배열/벡터 copy 와 memset  (0) 2020.12.11
c++ 3일차  (0) 2020.11.13
C++ string 사용법  (0) 2020.11.09
C++ - 2일차 백준 단계별로 풀기 5~7단계  (0) 2020.11.08

'알고리즘/알고리즘 관련 메모장'의 다른글

  • 현재글BFS , DFS 알고리즘 - 예제풀이

관련글

댓글

티스토리툴바