문제접근
놓쳤던 부분
•
인접행렬의 풀이와 인접리스트의 풀이를 할때 인덱스 접근이 조금씩 차이가 있는데 그 차이를 고려하지 않고 동일하게 풀이하여 계속적으로 오류가 있었음
코드
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);
}
C++
복사
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);
}
C++
복사
