[백준]1260번|DFS와BFS

헝 이 문제는 실패이다....

비주얼 스튜디오에서 돌렸을때는 적어도 내가 설정한 그래프에서는 돌아간다,,

하지만 백준에서 계속 시간초과가 나서 초기화 방식도 memset으로 바꾸어 보고 줄일 수 있는건 다 줄여본 것 같은데 그래도 시간초과가 났다,,,

그래서 찾아보니까 이 문제의 경우 인접행렬로 풀면 시간초과가 나기에 인접리스트나 간선리스트를 활용해야 한다고 한다..

나중에 수정본 올려보겠다.

#include<iostream>

#include <queue>

#include <memory.h>

#include <stack>

using namespace std;

#define MAX_VERTEX 1000

int map[MAX_VERTEX][MAX_VERTEX];

queue <int> BFS;

stack <int> DFS;

int visit[MAX_VERTEX];

int i, j;

void dfs(int vertex) {

int start = 1, tmp;

memset(visit, 0, sizeof(visit));

DFS.push(start);

while (!DFS.empty()) {

tmp = DFS.top();

if (visit[tmp] != 1)

cout << tmp << " ";

visit[tmp] = 1;

DFS.pop();

for (i = vertex; i >= 1; --i) {

if (i > tmp && map[tmp][i] == 1) {

DFS.push(i);

}

}

}

}

void bfs(int vertex) {

int start = 1, tmp;

    memset(visit, 0, sizeof(visit));

BFS.push(start);

while (!BFS.empty())

{

tmp = BFS.front();

if (visit[tmp] != 1)

cout << tmp << " ";

visit[tmp] = 1;

BFS.pop();

for (i = 1; i <= vertex; i++) {

if (i > tmp && map[tmp][i] == 1) {

BFS.push(i);

}

}

}

}

int main() {

int vertex, edge, start;

cin >> vertex >> edge >> start;

int v1, v2;

for(i =0; i < MAX_VERTEX; ++i)

memset(map[i], 0, sizeof(int) * MAX_VERTEX);

for (i = 0; i < edge; i++) {

cin >> v1 >> v2;

map[v1][v2] = map[v2][v1] = 1;

}

dfs(vertex);

cout << endl;

bfs(vertex);

return 0;

}