글 읽기 - DFS 질문입니다.

le_effort 4년 전 0

42-26 주석처리한 부분이 있으면 왜 안되는건가요? ㅠ

재귀로 구성되어있어 혼자 생각하려니 너무 어려워요 ㅠ

import java.util.*;
import java.io.*;

public class Main {
	static boolean visited[];	//각 정점에 대한 접근 개념으로 갈 것이니 1차원
	static int n;
	static int[][] arr;
	static int[][] ans;
	static int[] c;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr= new int[n+1][n+1];
		visited = new boolean[n+1];
		ans = new int[n+1][n+1];
		c = new int[n+1];
		for(int i=1; i<n+1; i++) {
			String[]t =br.readLine().split(" ");
			for(int j=1; j<n+1;j++) {
				arr[i][j]=Integer.parseInt(t[j-1]);	//방향 그래프 입력받음
			}
		}	//---입력끝 ---
		
		for(int i=1; i<n+1; i++) {
			dfs(i);	//정점에 대해서 탐색 실시
			for(int j=1; j<n+1; j++) {
				ans[i][j]=c[j];
			}
			visited = new boolean[n+1];
			c = new int[n+1];
		}
		
		for(int i=1;i<n+1;i++) {
			for(int j=1; j<n+1; j++) {
				System.out.print(ans[i][j]+" ");
			}
			System.out.println();
		}
		
	}
	public static void dfs(int x) {
		/*if(visited[x]) {
			return ;	// 한번 방문했던 것 이라면 굳이 다시 방문할 필요가 있을까?
		}
		visited[x] = true;*/
	// 이제 각 정점에 대해서 1로 연결된 부분 즉 다른 간선으로 갈 수 있는부분을 깊이탐색 해줘야함
		for(int i=1;i<n+1;i++) {
			if(arr[x][i] ==1 && !visited[i]) {
				c[i]=1;
				visited[i]= true;
				dfs(i);

			}
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS 질문입니다.

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말