경로 찾기

문제

가중치 없는 방향 그래프 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으로 출력해야 한다.

 

 

import java.util.*;

class Main {
	static int n;
	static int[][] graph;
	static boolean[] visited;
	static int[][] arr;	// 간선 (a->b) : arr[a][0] -> a , arr[a][1] -> b  
	static int[][] answer;
	static boolean find = false;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		graph = new int[n + 1][n + 1];
		visited = new boolean[n + 1];
		arr = new int[n + 1][2];
		answer = new int[n + 1][n + 1];

		int k = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph[i][j] = scan.nextInt();
				if (graph[i][j] == 1) {
					arr[k][0] = i;
					arr[k][1] = j;
					k++;
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					visited[i] = false;
				} else {
					visited[i] = true;
				}

				dfs(i, j);

				if (find == true) {
					answer[i][j] = 1;
				} else {
					answer[i][j] = 0;
				}

				visited[i] = false;
				find = false;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(answer[i][j] + " ");
			}
			System.out.println();
		}
	}

	static void dfs(int a, int b) {
		if (a == b && visited[a] == true) {
			find = true;
			return;
		}

		for (int i = 1; i <= n; i++) {
			if (arr[i][0] == a && visited[arr[i][1]] != true) {
				visited[arr[i][1]] = true;
				dfs(arr[i][1], b);
				visited[arr[i][1]] = false;
			}
		}
	}
}

 

처음 이렇게 짠 코드는 무슨 이유인지 모르게 런타임 에러가 떠서 다른 방법을 찾아 전역 변수를 줄이고 재귀 횟수도 줄여보았습니다.

 

import java.util.*;

class Main {
	static int n;
	static int[][] arr, result;

	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		arr = new int[n + 1][n + 1];
		result = new int[n + 1][n + 1];
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++)
				arr[i][j] = scan.nextInt();
		}
		// 한 줄씩 갈 수 있는곳을 모두 살펴보자.
		for (int i = 1; i <= n; i++)
			dfs(i, i);

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(result[i][j] + " ");
			}
			System.out.println();
		}
	}

	static void dfs(int start, int next) {
		// start(시작 점)을 따라서 갈 수 있는 곳을 다 돌아다녀본다.
		for (int i = 1; i <= n; i++) {
			// 원래 배열인 arr에서 1을 가르켜야 갈 수 있으며 갈 수 있다는 것은(맨 처음 next는 start)
			// start(시작 점)에서 갈 수 있으므로 1로 표시
			// result[start][i] 가 0이 아니라면 i는 이미 방문한 곳이므로 패스.
			if (arr[next][i] == 1 && result[start][i] == 0) {
				result[start][i] = 1;
				dfs(start, i);
			}
		}
	}
}

 

문제출처

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