문제접근🤔

놓쳤던 부분😅

인접행렬의 풀이와 인접리스트의 풀이를 할때 인덱스 접근이 조금씩 차이가 있는데 그 차이를 고려하지 않고 동일하게 풀이하여 계속적으로 오류가 있었음

코드😁

2296 KB

인접리스트 풀이

0 ms

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

int n, m, v;
std::vector<std::vector<int> > graph;
std::vector<int> visited;
std::queue<int> q;

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int node1, node2;

	std::cin >> n >> m >> v;
	graph.resize(n + 1);
	visited.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		std::cin >> node1 >> node2;
		graph[node1].push_back(node2);
		graph[node2].push_back(node1);
	}
	for (int i = 1; i <= n; i++)
		std::sort(graph[i].begin(), graph[i].end());
}

void dfs(int node)
{
	int next_node;

	visited[node] = 1;
	std::cout << node << " ";
	for (size_t i = 0; i < graph[node].size(); i++)
	{
		next_node = graph[node][i];
		if (!visited[next_node])
			dfs(next_node);
	}
}

void bfs(int node)
{
	int current;

	q.push(node);
	while (!q.empty())
	{
		current = q.front();
		visited[node] = 1;
		std::cout << current << " ";
		q.pop();
		for (int i = 0; i < graph[current].size(); i++)
			if (!visited[graph[current][i]])
			{
				visited[graph[current][i]] = 1;
				q.push(graph[current][i]);
			}
	}
}

void solution()
{
	dfs(v);
	std::cout << "\\n";
	std::fill(visited.begin(), visited.end(), 0);
	bfs(v);
}

int main(void)
{
	input_setting();
	input();
	solution();
	return (0);
}

6000 KB

인접행렬 풀이

8 ms

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

int n,m,v;
std::vector<int> visited;
std::vector< std::vector<int> > adj_matrix;
std::queue<int> q;

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int s,e;

	std::cin >> n >> m >> v;
	visited.resize(n + 1, 0);
	adj_matrix.resize(n + 1, std::vector<int>(n + 1, 0));
	for (int i = 0; i < m; i++)
	{
		std::cin >> s >> e;
		adj_matrix[s][e] = 1;
		adj_matrix[e][s] = 1;
	}
}

void dfs(int v)
{
	visited[v] = 1;
	std::cout << v << " ";
	for (int i = 1; i <= n; i++)
		if (adj_matrix[v][i] == 1 && visited[i] == 0)
			dfs(i);
	return ;
}

void bfs(int v)
{
	int current;

	q.push(v);
	while (!q.empty())
	{
		current = q.front();
		visited[current] = 1;
		std::cout << current << " ";
		q.pop();
		for (int i = 1; i <= n; i++)
			if (adj_matrix[current][i] == 1 && visited[i] == 0)
			{
				q.push(i);
				visited[i] = 1;
			}
	}
}

int main(void)
{
	input_setting();
	input();
	dfs(v);
    std::cout << "\\n";
	std::fill(visited.begin(), visited.end(), 0);
	bfs(v);
	return (0);
}