우주의WouldYou

요즘 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;

}

}

#include <iostream>

#include <queue>

using namespace std;

#define MAX_LINE 1000

int map[MAX_LINE][MAX_LINE] = { 0 };

int visited[MAX_LINE][MAX_LINE] = { 0 };

queue<pair<int, int>> q;

int tomatofind(int col, int row) {

int result = 0, i, j;

int dx[4] = { -1, 1, 0, 0 };

int dy[4] = { 0,0, -1, 1 };

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

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

if (map[i][j] == 0) continue;

else if (map[i][j] == 1) {

q.push(make_pair(i, j));

visited[i][j] = 1;

}

else if (map[i][j] == -1) visited[i][j] = 1;

}

}

while (!q.empty()) {

int y = q.front().first; //행

int x = q.front().second; //열

q.pop();

for (int k = 0; k < 4; k++) {

int nx = x + dx[k];

int ny = y + dy[k];

if (nx < 0 || nx >= col || ny < 0 || ny >= row) {

continue;

}

else if (visited[ny][nx] == 0 && map[ny][nx] == 0)

{

visited[ny][nx] = visited[y][x] + 1; //!

q.push(make_pair(ny, nx));

}

}

}

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

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

if (visited[i][j] == 0)return  -1;

else if (visited[i][j] > result) result = visited[i][j];

}

}

return result - 1;

}

int main() {

int row, col, i, j;

cin >> col >> row;

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

for (j = 0; j < col; j++)

cin >> map[i][j];

}

cout << tomatofind(col, row);

}

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

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

하지만 백준에서 계속 시간초과가 나서 초기화 방식도 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;

}

#include <iostream>

using namespace std;

#define MAX_VERTEX 30

int num;

int map[MAX_VERTEX][MAX_VERTEX];

int visit[MAX_VERTEX];

int queue[MAX_VERTEX];

int rear, front;

void bfs(int vertex) {

int i;

visit[vertex] = 1;

cout << vertex;

queue[rear++] = vertex; // ?

while (front < rear) {

vertex = queue[front++]; // ?

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

if (map[vertex][i] == 1 && !visit[i])

{

visit[i] = 1;

cout << i;

queue[rear++] = i;

}

}

}

}

int main() {

int T;

int test_case;

int i, j;

int start;

int v1, v2;

cin >> T;

for (test_case = 1; test_case <= T; test_case++) {

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

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

map[i][j] = 0;

}

visit[i] = 0;

queue[i] = 0;

}

front = 0;

rear = 0;

cin >> num >> start;

while (1) {

cin >> v1 >> v2;

if (v1 == -1 && v2 == -1)

break;

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

}

cout << test_case;

bfs(start);

cout << endl;

}

system("pause");

return 0;

}