[백준 11403] 경로 찾기

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> v[102];
int arr[102][102];
bool check[102][102];
int n;
void bfs(int start) {
    queue<int> q;
    q.push(start);
    
    while(!q.empty()) {
        int node=q.front(); q.pop();
        
        for(int i=1; i<=n; i++) {
            if (arr[node][i]==1 && check[start][i]==false) {
                check[start][i]=true;
                q.push(i);
            }
        }
    }
}
 
int main(void) {
    scanf("%d", &n);
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for(int i=1; i<=n; i++)
        bfs(i);
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            printf("%d ", check[i][j]);
        printf("\n");
    }
    
    return 0;
}

 

(+) 2019/10/10

DFS가 아닌 것 같은데...

#include<cstdio>
#include<cstring>
using namespace std;
int arr[102][102];
int ans[102][102];
bool check[102];
int n;
void dfs(int cur, int node) {
    check[node]=true;
    
    for(int i=1; i<=n; i++) {
        int next=arr[node][i];
        
        if(next!=0 && !check[i]) {
            ans[cur][i]=1;
            dfs(cur, i);
        }
        else if (next!=0 && check[i])
            ans[cur][i]=1;
        else {
            if(ans[node][i]!=0)
                continue;
        }
    }
}
int main(void) {
    scanf("%d", &n);
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    
    for(int i=1; i<=n; i++){
        memset(check,false,sizeof(check));
        dfs(i, i);
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            printf("%d ", ans[i][j]);
        printf("\n");
    }
    return 0;
}

 

(+) 플로이드-와샬 알고리즘이라는 것을 드디어 깨달았다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main{
    static int maxNum = 1000000000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        
        // 입력받기
        StringTokenizer st; int temp=0;
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine(), " ");
 
            for(int j=0; j<n; j++){
                temp = Integer.parseInt(st.nextToken());
                if(temp==0) arr[i][j] = maxNum;
                else arr[i][j] = temp;
            }
        }
 
        // 플로이드 와샬 알고리즘
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
                }
            }
        }
 
        // 
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j] == maxNum) sb.append("0").append(" ");
                else sb.append("1").append(" ");
            } sb.append("\n");
        }
 
        System.out.println(sb);
    }
}