[BOJ 11403] 경로 찾기 (Java, 그래프 탐색)

 

 

---

문제 링크

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

11403번: 경로 찾기

---

풀이 

- 단방향 그래프 문제 

 

예제 입력의 경우 아래와 같이 해석됨

예제 입력 1
3
0 1 0
0 0 1
1 0 0

예제 출력1
1 1 1
1 1 1
1 1 1

#정점(N)이 3개이고 간선이 존재한다는 뜻
1 -> 2
2 -> 3
3 -> 1

 

그래서 i = 1일때 1번 노드에서 방문 가능한 노드를 찾고 row 로 출력하면 되는 문제

i = 2일때 2번 노드에서 방문가능한 노드 찾아 row 출력 

i = 3일때 3번 노드에서 방문가능한 노드 찾아 row 출력

 

이때 해당 노드(i)의 경우 0으로 초기화하고 다른 노드 통해 방문 가능 여부 파악해야 함

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N;

    static List<Integer>[] adj;

    static int[] visit;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        adj = new ArrayList[N + 1];
        for(int i = 0; i <= N; i++) adj[i] = new ArrayList<>();

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++) {
                int value = Integer.parseInt(st.nextToken());
                if(value == 1) {
                    adj[i].add(j);
                }
            }
        }
    }

    static void initVisit() {
        if(visit == null) {
            visit = new int[N + 1];
        } else {
            for(int i = 1; i <= N; i++) {
                visit[i] = 0;
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);

        initVisit();

        while(!que.isEmpty()) {
            int x = que.poll();

            for(int y : adj[x]) {
                if(visit[y] == 0) {
                    visit[y] = 1;
                    que.add(y);
                }
            }
        }

        for(int i = 1; i <= N; i++) sb.append(visit[i]).append(' ');

    }

    static void pro() {
        for(int i = 1; i <= N; i++) {
            bfs(i);
            sb.append("\n");
        }

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }

}