[G5] 백준 14588번 Line Friends (Small) C++ 플로이드 와샬, 최단 거리

리뷰

 

https://www.acmicpc.net/problem/14588

간만에 풀어본 플로이드 와샬 문제, 재미있었다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• pos : 각 노드의 x좌표 범위를 저장할 변수
• dist : 각 노드간 거리를 저장할 2차원 정수 배열

 

함수

1. Init

void Init()
{
	for ( int i = 0; i < n; ++i )
		for ( int j = 0; j < n; ++j )
			dist[ i ][ j ] = 2e9;

	for ( int i = 0; i < n; ++i )
	{
		int l, r; cin >> l >> r;
		pos[ i ] = { l, r };
	}

	for ( int i = 0; i < n - 1; ++i )
	{
		for ( int j = i + 1; j < n; ++j )
		{
			const auto& [il, ir] = pos[ i ];
			const auto& [jl, jr] = pos[ j ];

			if ( ( jl <= il && il <= jr ) ||
				( jl <= ir && ir <= jr ) ||
				( jl <= il && ir <= jr ) ||
				( il <= jl && jr <= ir ) )
			{
				dist[ i ][ j ] = 1;
				dist[ j ][ i ] = 1;
			}
		}
	}
}

 

입력 및 초기화를 담당하는 함수

 

2. FloydWarshall

void FloydWarshall()
{
	for ( int k = 0; k < n; ++k )
	{
		for ( int i = 0; i < n; ++i )
		{
			for ( int j = 0; j < n; ++j )
			{
				if ( dist[ i ][ k ] == 2e9 ||
					dist[ k ][ j ] == 2e9 )
					continue;

				dist[ i ][ j ] = min( dist[ i ][ j ], dist[ i ][ k ] + dist[ k ][ j ] );
			}
		}
	}
}

 

플로이드 와샬을 통해 노드간 최단 거리를 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, Init함수를 호출해 입력과 pos, dist배열을 초기화한다.
2. FloydWarshall함수를 호출해 각 노드간의 최단 거리를 dist배열에 저장한다.
3. q값을 입력받고, q번의 쿼리 동안 두개의 노드 번호를 정보를 입력 받는다.
4. 두 노드간 거리가 초기값이라면 -1을, 아니라면 최단 거리를 출력 후 개행문자를 삽입해 줄바꿈을 수행한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 쿼리에서 노드의 번호가 1-based-indexing기반으로 들어오므로 1만큼 전위감소 시켜주었다.

 

정답 코드

#include <iostream>
using namespace std;
using pii = pair< int, int >;

const int N = 300;
int n, q;
pii pos[ N ];
int dist[ N ][ N ];

void Init()
{
	for ( int i = 0; i < n; ++i )
		for ( int j = 0; j < n; ++j )
			dist[ i ][ j ] = 2e9;

	for ( int i = 0; i < n; ++i )
	{
		int l, r; cin >> l >> r;
		pos[ i ] = { l, r };
	}

	for ( int i = 0; i < n - 1; ++i )
	{
		for ( int j = i + 1; j < n; ++j )
		{
			const auto& [il, ir] = pos[ i ];
			const auto& [jl, jr] = pos[ j ];

			if ( ( jl <= il && il <= jr ) ||
				( jl <= ir && ir <= jr ) ||
				( jl <= il && ir <= jr ) ||
				( il <= jl && jr <= ir ) )
			{
				dist[ i ][ j ] = 1;
				dist[ j ][ i ] = 1;
			}
		}
	}
}

void FloydWarshall()
{
	for ( int k = 0; k < n; ++k )
	{
		for ( int i = 0; i < n; ++i )
		{
			for ( int j = 0; j < n; ++j )
			{
				if ( dist[ i ][ k ] == 2e9 ||
					dist[ k ][ j ] == 2e9 )
					continue;

				dist[ i ][ j ] = min( dist[ i ][ j ], dist[ i ][ k ] + dist[ k ][ j ] );
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );
	cout.tie( 0 );

	cin >> n;
	Init();
	FloydWarshall();
	
	cin >> q;
	while ( q-- )
	{
		int f, t; cin >> f >> t;
		cout << (dist[--f][--t] != 2e9 ? dist[f][t] : -1 ) << '\n';
	}
}