글 읽기 - 경로 탐색 문제 질문입니다.. 어떻게 고쳐야 할까요

kke0949 8년 전 0

DFS를 이용해서 코드를 한번 짜보았습니다.

문제는 함수 진입 시에 시작점을 무조건 방문(visit[v] = 1)을 하게 되서

출력시 ans(0,0)이나 ans(1,1)등 두개가 같은 부분이 무조건 1이 나오게 됩니다

처음 시작점을 방문하는 부분을 빼면 재귀가 무한으로 돌아서 런타임 에러가 뜹니다;;

어떻게 고쳐야할까요 ㅠㅠ 다른 방식으로 풀어야할까요..

몇시간째 고민하다 도저히 모르겠어서 올립니다 ㅜㅜ도와주세요..

#include <iostream>
using namespace std;

int mtx[101][101];
int ans[101][101];
int visit[101];
int n;

void DFS(int v)
{
	visit[v] = 1;	//무조건 방문하면 안됨! 고쳐야 하는부분
	for (int i = 0; i < n; i++)
	{
		//가는 길이 있을때 & 방문하지 않았을 때
		if (mtx[v][i] == 1 && visit[i] == 0)
			DFS(i);
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			scanf("%d ", &mtx[i][j]);
	}

	for (int i = 0; i < n; i++)
	{
		DFS(i);

		//방문한 점을 결과 행렬에 넣음 & 초기화
		for (int j = 0; j < n; j++)
		{
			ans[i][j] = visit[j];
			visit[j] = 0;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			printf("%d ", ans[i][j]);
		puts("");
	}
}

isac322 8년 전 1

다른 알고리즘은 맞는데, 단지 \( i == j\)일때 0이 안나오는게 문제라면

다른건 전부 가만히 놔두고 출력할때 \( i == j \)이면 ans[i][j]대신 0을 출력하게하면 되지않을까요??

indioindio 8년 전 1

지금 당장은 visit[v]를 0, 1 이 아니라 방문한 횟수(최대 2)로 하고 DFS(v)가 끝난후에 visit[v]--;를 해주어서 0인지 1이상인지 확인하는 정도밖에 생각이 안 나네요.

kke0949 8년 전 1

말씀하신대로 방문횟수를 최대 2로 하고 i == j일때 2가 아니라면 0을 넣고 2라면 1로 숫자를 바꾸는 코드로 고쳐주니 맞았습니다!

두분 모두 감사합니다!

//DFS 함수
void DFS(int v)
{
	visit[v] += 1;   //무조건 방문하면 안됨! 고쳐야 하는부분
	for (int i = 0; i < n; i++)
	{
		//가는 길이 있을때 & 방문하지 않았을 때
		if (mtx[v][i] == 1 && visit[i] < 2)
			DFS(i);
	}
}

//메인문의 DFS 포문부분
	for (int i = 0; i < n; i++)
	{
		DFS(i);

		//방문한 점을 결과 행렬에 넣음 & 초기화
		for (int j = 0; j < n; j++)
		{
            //i==j면서 2가 안되었을때는 0으로
			if (i == j && visit[j] != 2)
			{
				ans[i][j] = 0;
				visit[j] = 0;
				continue;
			}
			ans[i][j] = visit[j];
			visit[j] = 0;
		}
	}

//출력부분
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
            //2인 경우 1로 고쳐줌
			if (ans[i][j] == 2)
				ans[i][j]--;
			printf("%d ", ans[i][j]);
		}			
		puts("");
	}

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

문제

문제

출처

ICPC

경로 탐색 문제 질문입니다.. 어떻게 고쳐야 할까요

kke0949 8년 전 0

isac322 8년 전 1

indioindio 8년 전 1

kke0949 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말