[백준]9372|상근이의여행

요즘 BFS를 공부중이라 해당 카테고리에 나와있는 문제를 푼 것인데, 내가 생각했을땐 DFS여야 최단 거리가 나오는거 같아 내 멋대로 바꾸었다..

하지만 이것도,,시간초과가 뜬다...50%정도 채점하다가,,,,,ㅜ

주어진 입력에서는 같은 결과가 나오지만 완전히 맞았는지는 불투명하다..

시간초과 문제가 반복되는걸로 보아 dfs, bfs등에서 시간초과를 해결할 방법을 찾아보아야 겠다ㅜ0ㅜ

#include<iostream>

#include<memory.h>

#include <stack>

using namespace std;

#define MAX_NATION 1000

int nat[MAX_NATION][MAX_NATION];

stack<int>s;

int start = 1, cnt;

int DFS(int total) {

int i, j, tmp;

s.push(start);

int first = start;

while (!s.empty()) {

tmp = s.top();

cnt++;

s.pop();

for (j = 0; j < total; j++) {

if (j > tmp && nat[tmp][j] == 1) {

if (j == first)

return cnt;

s.push(j);

}

}

}

return cnt;

}

int main() {

int test_case, nation, flight, i, j, k, tmp;

int v1, v2;

cin >> test_case;

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

memset(nat[i], 0, sizeof(nat[i]));

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

cnt = 0;

cin >> nation >> flight;

for (j = 0; j < flight; j++) {

cin >> v1 >> v2;

nat[v1][v2] = 1;

}

cout << DFS(nation) << endl;

}

}