[C] 백준 11403번 경로 찾기

링크
https://www.acmicpc.net/problem/11403

문제

---

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

---

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1

---

3
0 1 0
0 0 1
1 0 0

예제 출력 1

---

1 1 1
1 1 1
1 1 1

예제 입력 2

---

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

예제 출력 2

---

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

아이디어 스케치

---

• 이 문제에서 주어지는 인접 행렬에서는 i에서 j로 가는 길이가 양수인 경로, 즉 하나의 간선을 사이에두고 직접 연결되어 있는 경우에만 1로 주어지고, 이외에는 0으로 주어진다.
• a노드와 b노드가 직접 연결되어 있고, b노드와 c노드가 직접 연결되어 있으면 a노드와 c노드도 연결되어 있다는 아이디어로 이 문제에 접근하면 된다. a노드와 c가 연결되어 있는지 확인하기 위해서는 b와 같은 거쳐가는 노드가 필요하다. 즉 arr[a][b]==1, arr[b][c]==1이면 arr[a][c]==1이다.

코드 분할 설명

---

	scanf("%d", &N);	//N을 입력받음

	//2차원 배열 동적할당
	arr = (int**)calloc(N, sizeof(int*));	
	for (i = 0; i < N; i++) {
		arr[i] = (int*)calloc(N, sizeof(int));
	}

	//그래프의 인접 행렬 입력
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

• 먼저 정점의 개수 N을 입력받고 인접 행렬을 입력 받기 위해 2차원 배열을 동적할당받았다.
• 2차원 배열을 동적할당 받은 후 그래프의 인접 행렬을 입력받는다.

	for (k = 0; k < N; k++) {
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				if (arr[i][k] == 1 && arr[k][j] == 1)	// i정점과 k정점이 연결되어 있고, k정점과 j정점이 연결되어 있으면
					arr[i][j] = 1;	// i와 k도 연결되어 있음
			}
		}
	}

• 이 문제의 핵심부분으로 i정점과 k정점이 연결되어 있고(arr[i][k]==1), k정점과 j정점이 연결되어 있으면(arr[k][j]==1), i정점과 k정점도 연결되어 있다(arr[i][j]==1)라는 아이디어를 적용한 코드이다.
• 정점간에 연결여부를 확인하는 이 알고리즘은 이러한 부분문제를 해결하는 것부터 시작된다.

	//결과 행렬 출력
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}

• 결과 행렬을 출력한다.

전체코드

---

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int** arr;
	int N;
	int i, j,k;

	scanf("%d", &N);	//N을 입력받음

	//2차원 배열 동적할당
	arr = (int**)calloc(N, sizeof(int*));	
	for (i = 0; i < N; i++) {
		arr[i] = (int*)calloc(N, sizeof(int));
	}

	//그래프의 인접 행렬 입력
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

 
	for (k = 0; k < N; k++) {
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				if (arr[i][k] == 1 && arr[k][j] == 1)	// i정점과 k정점이 연결되어 있고, k정점과 j정점이 연결되어 있으면
					arr[i][j] = 1;	// i와 k도 연결되어 있음
			}
		}
	}

	//결과 행렬 출력
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}

	//2차원 배열 메모리 해제
	for (i = 0; i < N; i++)
		free(arr[i]);

	free(arr);

	return 0;
}

제출 결과

---