우주의WouldYou

#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;

}