인프런 커뮤니티 질문&답변

starkshn님의 프로필 이미지
starkshn

작성한 질문수

Do it! 알고리즘 코딩테스트 with C++

플로이드-워셜 (Floyd-Warshall)

백준 11404 플로이드 문제 질문있습니다.

작성

·

193

0

입력을 받을 때 

for	(int i = 0; i < m; ++i)
	{
		int a, b, c; cin >> a >> b >> c;
		for	(int i = 0; i < m; ++i)
	{
		int a, b, c; cin >> a >> b >> c;
		if (adj[a][b] > c) adj[a][b] = c;

위처럼 입력을 받았는데요

여기서 adj[a][b] = c;이게 빠지면 틀렸다라고 나오는데 왜 틀린것인지 이해가 안가는데 설명 부탁드립니다..

c++코딩-테스트알고리즘

답변 1

0

인프런 AI 인턴님의 프로필 이미지
인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

starkshn님, 질문하신 부분에 대해 설명드리겠습니다.

백준 11404번 플로이드 문제에서는 한 도시에서 다른 도시로 가는 노선이 여러 개 있을 수 있습니다. 이 때 각 노선마다 비용이 다를 수 있기 때문에, 가능한 가장 적은 비용의 노선을 선택해야 합니다.

코드의 adj[a][b] = c; 부분은 도시 a에서 도시 b로 가는 비용을 배열에 저장하는 부분입니다. 이 때 if (adj[a][b] > c) 조건문은 이미 저장되어 있는 노선의 비용보다 더 저렴한 비용의 노선이 입력으로 들어오면 해당 비용으로 갱신하라는 의미입니다.

만약 이 부분이 빠지면, 여러 개의 노선 중에 최소 비용이 아닌 마지막에 입력된 노선의 비용으로 배열이 저장될 수 있습니다. 그러면 알고리즘 상 최소 비용으로 모든 도시를 연결하는 것이 아니라 잘못된 값을 참조하게 되므로 문제의 해답이 정확하지 않게 됩니다.

따라서 adj[a][b] > c 조건으로 노선의 최소 비용을 저장하는 과정은 정확한 최단 경로를 구하는 데 필수적인 부분입니다.

starkshn님의 프로필 이미지
starkshn

작성한 질문수

전체 Q&A
질문하기