1260 - DFS와 BFS

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <queue>

#include <vector>

using namespace std;

int VN, E, S;

int V[1001][1001];

bool BFS_visited[1001];

bool DFS_visited[1001];

void BFS(int x)

{

queue<int> Q;

BFS_visited[x] = true;

Q.push(x);

while (!Q.empty())

{

int x = Q.front(); Q.pop();

cout << x << " ";

for (int i = 1; i <= VN; i++)

{

if (V[x][i] == 1 && BFS_visited[i] != true)

{

BFS_visited[i] = true;

Q.push(i);

}

}

}

}

void DFS(int x)

{

DFS_visited[x] = true;

cout << x << " ";

for (int i = 1; i <= VN; i++)

{

if (V[x][i] == 1 && DFS_visited[i] != true)

{

DFS(i);

}

}

}

int main()

{

cin >> VN >> E >> S;

int r, c;

for (int i = 0; i < E; i++)

{

cin >> r >> c;

V[r][c] = 1;

V[c][r] = 1;

}

DFS(S);

cout << endl;

BFS(S);

return 0;

}

양방향 그래프이기 때문에 

V[r][c] = 1;

V[c][r] = 1;

모두 1을 해줘야 한다. 이부분에서 조금 헷갈렸다.

그리고 배열의 크기 조심할 것.

배열의 크기를 V[10001][10001] 으로 했는데 런타임 에러가 났다. 400메가 정도의 크기라고 질문 게시판을통해 알게 되었다.