문제
가중치 없는 방향 그래프 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문제 풀이
package com.ssafy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ11403 {
static boolean[] visited;
static int[][] graph;
static int N;
static int[][] result;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
StringTokenizer st;
graph=new int[N][N];
result=new int[N][N];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
graph[i][j]=Integer.parseInt(st.nextToken());
}
}
//dfs
for(int i=0;i<N;i++){
//i번째 노드에서 출발한다고 생각
//새로운 노드를 잡으면 방문 배열도 초기화 해줘야함
visited=new boolean[N];
dfs(i);
//dfs를 거쳐서 모든 이어진 노드를 방문했다면 visited[i]=true
//즉 false라는 것은 해당 노드에서 출발했을 때 도달하지 못한다는 뜻임
for(int j=0;j<N;j++){
if(visited[j]) result[i][j]=1;
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.print(result[i][j]+" ");
}
System.out.println();
}
}
private static void dfs(int node){
for(int i=0;i<N;i++){
if(graph[node][i]==1 && !visited[i]){
visited[i]=true;
dfs(i);
//방문하고 길을 잘못들어서 빠져나와야할 이유는 없으니 백트래킹 하지 않음
}
}
}
}DFS를 이용해서 i번째 정점에서 출발했을 때 방문할 수 있는 정점들을 모두 방문하고 방문했는지 안 했는지 체크해서 답을 출력했다.
DFS 함수
private static void dfs(int node){
for(int i=0;i<N;i++){
if(graph[node][i]==1 && !visited[i]){
visited[i]=true;
dfs(i);
//방문하고 길을 잘못들어서 빠져나와야할 이유는 없으니 백트래킹 하지 않음
}
}
}DFS의 기본 로직을 통해 구현한다.
해당 출발 노드에서 연결되어있고 방문하지 않은 모든 정점들을 dfs 호출하여 방문체크해준다.
if문을 통해 종료조건을 따로 주지 않아도 되는 이유는 for문 안에 있는 if문에서 방문한 정점이라면 dfs 호출하지 않기 때문에 방문할 수 있는 정점들을 모두 방문하면 자연스럽게 메인으로 돌아온다.
연결되어있는 모든 정점들을 방문하고 나면 dfs 호출이 끝이난다.
DFS 함수 호출
for(int i=0;i<N;i++){
//i번째 노드에서 출발한다고 생각
//새로운 노드를 잡으면 방문 배열도 초기화 해줘야함
visited=new boolean[N];
dfs(i);
//dfs를 거쳐서 모든 이어진 노드를 방문했다면 visited[i]=true
//즉 false라는 것은 해당 노드에서 출발했을 때 도달하지 못한다는 뜻임
for(int j=0;j<N;j++){
if(visited[j]) result[i][j]=1;
}
}출발하는 정점마다 dfs 탐색을 돌려줘야하기 때문에 for문을 통해 출발하는 정점들을 매개변수로 보내주어 반복한다.
이때 방문했는지 체크해야하는 배열은 출발하는 정점이 바뀔때마다 초기화해준다.
i번째 정점을 출발선으로 했을 때의 dfs가 끝나면 visited 배열을 통해 방문한 정점과 방문하지 않은 정점을 체크하여 1과 0을 넣어준다.
DFS로 풀 수 있을 것 같아서 DFS 탐색으로 문제를 풀었고 제출까지 완료했지만 이 문제는 플로이드-워셜로 분류되어있다.
간단하게 말하자면 플로이드-워셜은 모든 지점에서 다른 지점까지의 최단경로를 구할 때 사용하는 알고리즘으로
i -> j 정점으로 이동할 때 1번 ~ N번까지의 정점을 거쳐서 j로 도달하는 경우와 직접적으로 j로 도달하는 경우 중 최소비용을 선택하는 방식이다.
for(int k=0;k<N;k++){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
graph[i][j]=Math.min(graph[i][j], graph[i][k]+graph[k][j]);
}
}
}기본 코드는 위와 같다.
이러한 방식을 이용해서 11403번 문제도 풀 수 있는데 이 문제는 최소비용이 없기 때문에 연결이 되어있는지만 확인하면 된다.
플로이드-워셜 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static boolean[] visited;
static int[][] graph;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
StringTokenizer st;
graph=new int[N][N];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
graph[i][j]=Integer.parseInt(st.nextToken());
}
}
for(int k=0;k<N;k++){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(graph[i][k]==1 && graph[k][j]==1){
graph[i][j]=1;
}
}
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.print(graph[i][j]+" ");
}
System.out.println();
}
}
}3중 for문을 확인해보면 위에서 적었던 플로이드-워셜 코드와 흡사한 것을 확인할 수 있다.
두 가지 방식으로 제출했을 때 메모리와 시간은 아래처럼 나왔다.
위가 플로이드-워셜, 아래가 DFS
엄청 시간이 차이나지도 않고 메모리는 오히려 플로이드-워셜이 더 많이 차지한 것을 확인할 수 있었다.
