[백준] 단계별로 풀어보기 > DFS와 BFS (c++)

문제 1. DFS와 BFS

#include <iostream>
#include <vector>
#include <algorithm> 
#include <cstring> 
#include <queue> 

using namespace std;

void func_1260_dfs_recursion(int n, vector<int> * graph, bool* visited) {
	visited[n] = true;
	cout << n << " ";

	for (auto node : graph[n]) {
		if (!visited[node]) {
			func_1260_dfs_recursion(node, graph, visited);
		}
	}
}

void func_1260_bfs_queue(int n, vector<int> * graph, bool* visited) {
	queue<int> q;
	int now_node;

	visited[n] = true;
	q.push(n);

	while (!q.empty()) {
		now_node = q.front();
		q.pop();
		cout << now_node << " ";

		for (auto node : graph[now_node]) {
			if (!visited[node]) {
				visited[node] = true;
				q.push(node);
			}
		}
	}
	cout << "\n";
}

int main() {
	int n, m, start_node, u, v;
	
	cin >> n >> m >> start_node;

	vector<int> *graph = new vector<int>[n+1];

	bool *visited = new bool[n+1];
	memset(visited, 0, sizeof(bool) * (n+1));

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
    
	func_1260_dfs_recursion(start_node, graph, visited);
	cout << "\n";

	memset(visited, 0, sizeof(bool) * (n + 1));
	func_1260_bfs_queue(start_node, graph, visited);
    
	return 0;
}

 

문제 2. 바이러스

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> 

using namespace std;

static int func_2606_cnt;

void func_2606_dfs(int start, vector<int> *graph, bool* visited) {
	visited[start] = true;

	func_2606_cnt++;

	for (auto node : graph[start]) {
		if (!visited[node]) {
			func_2606_dfs(node, graph, visited);
		}
	}
}

int main() {
	int n, m, u, v;

	cin >> n >> m;

	vector<int> *graph = new vector<int>[n+1];

	bool* visited = new bool[n+1];
	memset(visited, 0, sizeof(bool) * (n+1));

	func_2606_cnt = 0;

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
    
	func_2606_dfs(1, graph, visited);

	cout << func_2606_cnt -1 << "\n";
    
	return 0;
}

 

문제 3. 단지 번호 붙이기

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<utility> 

using namespace std;

int func_2667_bfs(int cnt, int n, queue<pair<int, int>> q, int **map, int ** v) {
	int _x, _y, a=0;
	pair<int, int> now, tmp;

	int** direc = new int* [4];
	for (int i = 0; i < 4; i++) {
		direc[i] = new int[2];
		if (i == 0) {
			_x = 0;
			_y = -1;
		}
		else if (i == 1) {
			_x = 1;
			_y = 0;
		}
		else if (i == 2) {
			_x = 0;
			_y = 1;
		}
		else if (i == 3) {
			_x = -1;
			_y = 0;
		}
		direc[i][0] = _x;
		direc[i][1] = _y;
	}

	while (!q.empty()) { 
		now = q.front();
		q.pop();
		if (v[now.first][now.second] != 1) {
			v[now.first][now.second] = 1;
			a++;
		}

		for (int i = 0; i < 4; i++) {
			_x = now.first + direc[i][0];
			_y = now.second + direc[i][1];

			if (_x < 0 || _x >= n) {
				continue;
			}
			if (_y < 0 || _y >= n) {
				continue;
			}
			
			if (map[_x][_y] == 0) {
				continue;
			}

			if (v[_x][_y] == 1) {
				continue;
			}

			// 방문한적 없는 좌표인데 값이 1보다 크면 현재 카운트로 덮어쓰기 및 방문처리
			if (map[_x][_y] >= 1) {
				v[_x][_y] = 1;
				map[_x][_y] = cnt;
				q.push({_x, _y});
				//cout << _x << ", " << _y << "\n";
				a++;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		delete direc[i];
	}

	return a;
}

int main() {
	int n, cnt =0;
	string str;
	queue<pair<int, int>> q;
	vector<int> m;
	int tmp_m;

	cin >> n;

	int** v = new int* [n];
	for (int i = 0; i < n; i++) {
		v[i] = new int[n];
		for (int j = 0; j < n; j++) {
			v[i][j] = 0;
		}
	}

	int** _map = new int* [n];
	for (int i = 0; i < n; i++) {
		str = "";
		_map[i] = new int[n];

		cin >> str;
		for (int j = 0; j < n; j++) {
			_map[i][j] = str[j] - '0';
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (_map[i][j] == 1) {
				q.push({ i, j });
				
				tmp_m = func_2667_bfs(cnt+1, n, q, _map, v);
				if (tmp_m != 0) {
					m.push_back(tmp_m);
					cnt++;
				}
			}
			
		}
	}

	sort(m.begin(), m.end());

	cout << cnt << "\n";
	for (int i = 0; i < cnt; i++) {  
		cout << m[i] << "\n";
	}
    return 0;
}

 

문제 4. 유기농 배추

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

using namespace std;

int main() {
	int test_case;
	int n, m, k;
	int u, v;
	int _x, _y;
	pair<int, int> dir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // 상, 우, 하, 좌
	pair<int, int> tmp_q;
	int graph_count = 0;

	int** _map;
	int** _visit;
	queue<pair<int, int>> q;


	cin >> test_case;
	for (int a = 0; a < test_case; a++) {
		cin >> m >> n >> k;

		// Map 생성 및 초기화
		_map = new int* [n];
		_visit = new int* [n];

		for (int i = 0; i < n; i++) {
			_map[i] = new int[m];
			_visit[i] = new int[m];

			memset(_map[i], 0, sizeof(int) * m);
			memset(_visit[i], 0, sizeof(int) * m);

		}

		// Map 업데이트
		for (int i = 0; i < k; i++) {
			cin >> u >> v;
			_map[v][u] = 1;
		}

		graph_count = 0;


		// Map 탐색
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				// 지도에서 현재 좌표가 1이고 방문한 적이 없으면 현재 좌표를 q에 등록하고 방문 처리
				if (_map[i][j] == 1 && _visit[i][j] != 1) {
					q.push({i, j});
					_visit[i][j] = 1;
					
					graph_count++;
				}

				// q에 값이 있으면
				while (!q.empty()) {
					tmp_q = q.front();
					q.pop();
					
					// 현재 좌표에서 인접한 4방향 좌표를 검사, 위부터 시계방향
					for (int i = 0; i < 4; i++) {
						_x = tmp_q.first + dir[i].first;
						_y = tmp_q.second + dir[i].second;

						// 경계선 검사
						if (_x >= n || _x < 0)
							continue;

						if (_y >= m || _y < 0) 
							continue;

						// 값 검사
						if (_map[_x][_y] == 0)
							continue;
						
						// 방문여부 검사
						if (_visit[_x][_y] == 1)
							continue;

						// 방문기록 남기고 다음 작업대상에 추가
						_visit[_x][_y] = 1;
						q.push({_x, _y});
					}
				}
			}
		}

		cout << graph_count << "\n";

		// 메모리 해제
		for (int i = 0; i < n; i++) {
			free(_map[i]);
			free(_visit[i]);
		}
	}
    
    return 0;
}

 

문제 5. 미로 탐색

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

// 노드 정보 저장용 클래스
class func_2178_node {
public:
	int x;
	int y;
	int value;
	int visited;
};

int func_2178_BFS(int n, int m, func_2178_node **_map, int *start_node, int *end_node) {
	// BFS 탐색을 위한 큐 생성 현재 노드 저장
	queue<func_2178_node> q;
	func_2178_node tmp_node, now_node;

	// 상0, 우1, 하2, 좌3 
	int** direction = new int*[4];
	for (int i = 0; i < 4; i++) {
		direction[i] = new int[2];

		if (i == 0) {
			direction[i][0] = 0;
			direction[i][1] = -1;
		}
		if (i == 1) {
			direction[i][0] = 1;
			direction[i][1] = 0;
		}
		if (i == 2) {
			direction[i][0] = 0;
			direction[i][1] = 1;
		}
		if (i == 3) {
			direction[i][0] = -1;
			direction[i][1] = 0;
		}
	}


	// 시작노드의 방문 여부 변경
	_map[start_node[0]][start_node[1]].visited = 1;
	// 시작노드 넣기
	q.push(_map[start_node[0]][start_node[1]]);

	// 큐에 값이 있으면 탐색 시작
	while (!q.empty()) {
		// 현재 큐의 값 가져오기 + pop
		now_node = q.front();
		q.pop();

		// 인접 노드 탐색 (시계방향으로 탐색)
		for (int i = 0; i < 4; i++) {
			// 현재 좌표가 좌우를 넘어가는지 확인
			if (now_node.x + direction[i][0] <= 0 || now_node.x + direction[i][0] > n) {
				continue;
			}

			// 현재 좌표가 상하를 넘어가는지 확인
			if (now_node.y + direction[i][1] <= 0 || now_node.y + direction[i][1] > m) {
				continue;
			}

			// 이동한 값이 맵 안에 있으면 노드 이동
			tmp_node = _map[now_node.x + direction[i][0]][now_node.y + direction[i][1]];

			// 값이 1이 아닌지 검사, 아니면 continue;
			if (tmp_node.value == 0) {
				continue;
			}

			// 방문 여부가 없는지 검사 (방문했으면 다음거)
			if (tmp_node.visited) {
				continue;
			}

			_map[tmp_node.x][tmp_node.y].visited = _map[now_node.x][now_node.y].visited + 1;
			q.push(_map[tmp_node.x][tmp_node.y]);
		}
	}

	return _map[n][m].visited;
}

int main() {
	int n, m;
	int* start_node = new int[2];
	int* end_node = new int[2];
	string str_input;

	cin >> n >> m;

	start_node[0] = 1;
	start_node[1] = 1;
	end_node[0] = n;
	end_node[1] = m;

	func_2178_node** map = new func_2178_node*[n+1];
	for (int i = 1; i <= n; i++) {
		map[i] = new func_2178_node[m+1];
	}

	for (int i = 1; i <= n; i++) {
		cin >> str_input;
		for (int j = 1; j <= m; j++) {
			map[i][j].x = i;
			map[i][j].y = j;
			map[i][j].value = str_input[j-1] - '0';
			map[i][j].visited = 0;
		}
	}

	cout << func_2178_BFS(n, m, map, start_node, end_node) << "\n";

    return 0;
}

 

문제 6. 토마토

#include <iostream>
#include <queue> 

using namespace std;

class func_7576_tomato {
public:
	int x;
	int y;
	int visited;
	int value;
};

void func_7576_bfs(int n, int m, func_7576_tomato** box, queue<func_7576_tomato> q) {
	func_7576_tomato now_tomato, tmp_tomato;

	// 방향 정의 (시계방향)
	int** direc = new int*[4];
	int _x, _y;
	for (int i = 0; i < 4; i++) {
		direc[i] = new int[2];

		// 상
		if (i == 0) {
			_x = 0;
			_y = -1;
		}
		// 우
		if (i == 1) {
			_x = 1;
			_y = 0;
		}
		// 하
		if (i == 2) {
			_x = 0;
			_y = 1;
		}
		// 좌
		if (i == 3) {
			_x = -1;
			_y = 0;
		}

		direc[i][0] = _x;
		direc[i][1] = _y;
	}

	// bfs 탐색 시작 
	while (!q.empty	()) {
		now_tomato = q.front();
		q.pop();

		// 각 방향별 탐색
		for (int i = 0; i < 4; i++) {
			// 이동한 범위가 토마토 상자 내부인지 검사 (x축)
			if (now_tomato.x + direc[i][0] < 0 || now_tomato.x + direc[i][0] >= n) {
				continue;
			}
			// 이동한 범위가 토마토 상자 내부인지 검사 (y축)
			if (now_tomato.y + direc[i][1] < 0 || now_tomato.y + direc[i][1] >= m) {
				continue;
			}

			tmp_tomato = box[now_tomato.x + direc[i][0]][now_tomato.y + direc[i][1]];

			// 해당 위치가 벽인지 검사
			if (tmp_tomato.value != 0) {
				continue;
			}

			// 해당 위치에 숙성되지 않은 토마토가 있으면 숙성 시키고 몇 일차에 숙성시켰는지 입력 후 큐에 등록
			box[tmp_tomato.x][tmp_tomato.y].value = 1;
			box[tmp_tomato.x][tmp_tomato.y].visited = now_tomato.visited + 1;
			q.push(box[tmp_tomato.x][tmp_tomato.y]);
		}
	}
}

int main() {
	int m, n, tmp, max;
	queue<func_7576_tomato> q;

	// 노드 개수
	cin >> m >> n;

	// 노드 생성
	func_7576_tomato** box = new func_7576_tomato*[n];
	for (int i = 0; i < n; i++) {
		box[i] = new func_7576_tomato[m];
	}

	// 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			box[i][j].x = i;
			box[i][j].y = j;
			box[i][j].visited = 0;
			box[i][j].value = 0;
		}
	}

	// 입력값 받기, 입력에 따른 값 설정
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tmp;
			box[i][j].value = tmp;
			
			//입력 값이 1이면 큐에 등록
			if (tmp == 1) {
				q.push(box[i][j]);
			}
		}
	}

	func_7576_bfs(n, m, box, q);

	max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 숙성안된 토마토가 있으면 -1
			if (box[i][j].value == 0) {
				max = -1;
				break;
			}
			// 최대값 찾아서 갱신
			if (max < box[i][j].visited) {
				max = box[i][j].visited;
			}
		}
		if (max == -1) {
			break;
		}
	}

	cout << max << "\n";
    
	return 0;
}

 

문제 7. 토마토

 

문제 8. 숨바꼭질

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

void func_1697_bfs(int k, queue<int> q, int *visited) {
    int now;
    while (!q.empty()) {
        now = q.front();
        q.pop(); 

        if (now == k) {
            break;
        }

        if (visited[now - 1] == 0 && (now - 1) >= 0) {
            visited[now - 1] = visited[now] + 1;
            q.push(now-1);
        }

        if ( (now+1) < 100000 && visited[now + 1] == 0) {
            visited[now + 1] = visited[now] + 1;
            q.push(now+1);
        }
        
        if ( (now * 2) <= 100000 && visited[now * 2] == 0) {
                visited[now * 2] = visited[now] + 1;
                q.push(now * 2);
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    
    int* visited = new int[100000];
    memset(visited, 0, sizeof(int) * 100000);
    queue<int> q;

    q.push(n);
    visited[n] = 1;
    func_1697_bfs(k, q, visited);

    cout << visited[k]-1 << "\n";
    
    return 0;
}

 

문제 9. 벽 부수고 이동하기

 

문제 10. 나이트의 이동

 

문제 11. 이분 그래프

 

결과