글 읽기 - dfs 시간초과 질문입니다.

gmldus0407 4년 전 0

dfs 기본으로 구현했는데 시간초과가 떠서요 ㅜㅜ 이 문제자체가 dfs말고 다른방식( floyd)로 풀어야하는건가요 아님 dfs를이용하되여기서 시간을 줄일수 있는 방법이 더 있을까요?ㅠㅠㅠ

#include <iostream>
#include <cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int a, N;
vector<pair<int, int> >v[100];
int map[100][100];
int found = 0, cnt = 0;
bool visited[100][100];



void dfs(int x, int h) {

	if (x == h && cnt!=0) {
		found = 1;
		return;
	}
	for (int i = 0; i < v[x].size(); i++) {
		if (visited[v[x][i].first][v[x][i].second] == false) {
			visited[v[x][i].first][v[x][i].second] = true;
			cnt++;
			dfs(v[x][i].second,h);
			visited[v[x][i].first][v[x][i].second] = false;
		}
	}
	
}

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a;
			map[i][j] = a;
			if (a == 1) v[i].push_back(make_pair(i,j));
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) cout << "1 ";
			else {
				dfs(i,j);
				if (found == 1) cout << "1 ";
				else if (found == 0) cout << "0 ";
			}
			found = 0;
			cnt = 0;
		}
		cout << "\n";
	}
}

yehyun 4년 전 0

일단 저는 나이브한 dfs로 풀어서 억셉 받았습니다.

의심이 가는 부분은,

질문자님께서 작성하신 dfs의 visited가 edge를 방문했는가를 기록하고 있는데,

그러면 같은 node를 매우 많이 방문하는 경우가 생길 수 있어서 좋지 않습니다.

visited를 일차원 배열로 두어서 edge가 아닌 node를 방문했는가를 기록하는 방식으로 고치시는 게 좋을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs 시간초과 질문입니다.

gmldus0407 4년 전 0

yehyun 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말