글 읽기 - 3중 for문으로 하는 이유를 모르겠습니다.

sj155 4년 전 0

모르겠어서 다른 분들의 코드 보고 3중 for문이 많다는 것을 알게 되었습니다.

2중 for문으로 하면 문제가 풀리지 않는 이유를 알고 싶습니다.(아니면 제가 짠 코드가 잘못된 건가요)

유니온 파인드를 사용한 이유는 서로만 연결되어 있는 도시끼리 음수 사이클을 가지는 경우 출발점에서 도달하지 못하기 때문입니다.

#include <iostream>

using namespace std;

#define INF 10000000

int disjoint[501];

int find(int x)
{
	if (disjoint[x] == x)//부모가 자신인 경우 그냥 반환
	{
		return x;
	}

	return disjoint[x] = find(disjoint[x]);
}

void merge(int x, int y)
{
	int a = find(x);
	int b = find(y);

	//작은 쪽이 부모가 된다

	if (a > b)
	{
		disjoint[a] = b;
	}
	else if(a < b)
	{
		disjoint[b] = a;
	}
}

int main()
{
	int n, m, city[501], line[6001][3];

	cin >> n >> m;

	city[1] = 0;
	disjoint[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		city[i] = INF;//각 도시 거리 무한
		disjoint[i] = i;//각 도시의 부모는 자신
	}

	for (int i = 1; i <= m; i++)
	{
		cin >> line[i][0] >> line[i][1] >> line[i][2];
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (city[line[j][0]] + line[j][2] < city[line[j][1]])//relaxation을 해줍니다
			{
				city[line[j][1]] = city[line[j][0]] + line[j][2];

				merge(line[j][0], line[j][1]);//도시가 연결된 경우 합쳐줍니다
			}
		}
	}
	
	for (int j = 1; j <= m; j++)
	{
		if (city[line[j][0]] + line[j][2] < city[line[j][1]])//이제 바뀌는 경우 음수 사이클이 존재한다는 뜻입니다
		{
			if (find(line[j][1]) == 1)//부모가 1인 지점이면 1에서 도시까지 갈때 음수 사이클이 존재합니다
			{
				cout << -1;

				return 0;
			}
		}
	}

	for (int i = 2; i <= n; i++)
	{
		if (INF == city[i])
		{
			printf("-1\n");
		}
		else
		{
			printf("%d\n", city[i]);
		}
	}

	return 0;
}

djm03178 4년 전 0

3중 for문이 단순한 아이디어에서 나오는 것이 아니라 벨만 포드라는 알고리즘을 사용한 것입니다.

sj155 4년 전 0

제 생각에 대한 설명이 부족했던것 같습니다.

이 문제는 벨만 포드 알고리즘으로 푸는 것을 알고 있습니다.

저는 2중 for문으로도 풀 수 있다고 생각합니다.

그런데 2중 for문으로는 다른 분들의 글을 보고 코드를 복사해서 돌려봐도 틀렸다고 나와서

3중 for문으로 푸는 방법을 알고 싶습니다.

djm03178 4년 전 1

3중 for문이 어떤 코드를 보셨는지는 모르겠는데 지금 코드랑 다를 게 없습니다. 아마도 그 코드들은 간선 정보를 크기 m의 배열에 모으는 대신 시작점에 따라 나누어서 저장했기 때문에 [n번의 루프 동안 {모든 시작점에 대해 (각 시작점에서 나가는 간선들을 확인)}] 하는 방식으로 구현했을 것입니다.

이 코드는 그냥 다음과 같은 입력이 반례입니다.

2
3 -1
2 -1

djm03178 4년 전 1

그리고 inf값도 너무 작아서 1번과의 연결 여부도 올바르게 판정을 할 수 없습니다.

sj155 4년 전 0

답변 감사합니다.

좀 더 생각해보겠습니다.

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

문제

문제

출처

ICPC

3중 for문으로 하는 이유를 모르겠습니다.

sj155 4년 전 0

djm03178 4년 전 0

sj155 4년 전 0

djm03178 4년 전 1

djm03178 4년 전 1

sj155 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말