[백준 11403] 경로 찾기 (JAVA)

백준 11403번 문제 - 경로 찾기

11403번: 경로 찾기

---

문제 분석 

 

 

• 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
  • 자기 자신에게 오는 것도 양수여야지 1로 (돌아서 자기자신으로 돌아와야함 0은 안됨)

---

해결 포인트

 

• BFS 사용
• 가운데 대각선 (자기자신 생각) 
  • 사이클이 있어야한다. (돌아서 자기자신한테 와야한다)
  • 자기자신을 처음 visit를 true로 하지 말자. 

---

코드

 

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

public class Main {
    public static int [][] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        nums = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                nums[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            BFS(i, N);
            for (int j = 0; j < N; j++) {
                bw.write(nums[i][j] + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }

    public static void BFS(int index, int N) {
        boolean [] visit = new boolean[N];
        Queue<Integer> queue = new LinkedList<>();

        queue.add(index);

        while (!queue.isEmpty()) {
            int value = queue.poll();
            for (int i = 0; i < N; i++) {
                if(nums[value][i] == 1 && !visit[i]) {
                    nums[index][i] = 1;
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}