[백준] 11403번 경로 찾기 (C++, JAVA)

11403번: 경로 찾기

모든 정점을 둘러보며 현재 정점이 가리키는 정점을 다시 현재 정점으로 삼는 방식으로

재귀로 DFS를 구현했다.

한 번 방문한 정점은 visited로 표시해준 후 다시는 방문하지 않도록 해주었다.

 

한 정점의 연결고리 검사가 모두 끝나면 visited를 0으로 다시 초기화해주고

그다음 정점의 연결고리들을 모두 검사해준다.

 

< C++ 코드 >

#include <iostream>
using namespace std;

void Dfs(int N, int idx, int graph[][101], int visited[]) {
	for (int i = 0; i < N; i++) {
		if (!visited[i] && graph[idx][i]) {
			visited[i] = 1;
			Dfs(N, i, graph, visited);
		}
	}
}

int main() {
	int N;
	cin >> N;
	int graph[101][101] = { 0 };
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> graph[i][j];

	for (int i = 0; i < N; i++) {
		int visited[101] = { 0 };
		Dfs(N, i, graph, visited);
		for (int j = 0; j < N; j++) if (visited[j]) graph[i][j] = 1;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cout << graph[i][j] << " ";
		cout << "\n";
	}

	return 0;
}

 

< JAVA 코드 >

import java.util.Scanner;

public class BOJ_11403_경로찾기 {
	private static int N;
	private static int arr[][];
	private static boolean visited[];
	
	public static void dfs(int start, int x) {
		for(int i = 0; i < N; i++) {
			if(arr[x][i] == 1 && !visited[i]) {
				arr[start][i] = 1;
				visited[i] = true;
				dfs(start, i);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); arr = new int[N][N];
		for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) arr[i][j] = sc.nextInt();
		for(int i = 0; i < N; i++) {
			visited = new boolean[N];
			dfs(i, i);
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) System.out.print(arr[i][j] + " ");
			System.out.println();
		}
	}
}