BOJ#11403 경로찾기

BOJ#11403 경로찾기

* 문제

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

* 풀이

가중치 없는 방향 그래프가 행렬로 주어졌을 때, i에서 j로 가는 경로 유무를 행렬로 표현하라.

bfs(Breadth First Search)를 이용하였다.

1. bfs(i, j) : i를 시작점으로 해서 연결된 모든 노드를 탐색한다. j를 찾을 경우 return.

2. 위 과정에서 탐색한 노드는 중복해서 탐색하지 않도록 한다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%2311403_BFS_FindPath/src/Main.java

Java (17.08.29)

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

   static int N;
   static int[][] map = new int[101][101];

   public static void main(String[] args) throws IOException {

      // Input
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

      for (int i = 0; i < N; i++) {

         StringTokenizer st = new StringTokenizer(br.readLine());
         for (int j = 0; j < N; j++) {

            map[i][j] = Integer.parseInt(st.nextToken());
         }
      }

      // Solve
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {

            bw.write(solve(i, j) + " ");
         }
         bw.write("\n");
      }

      bw.flush();

      bw.close();
      br.close();
   } // ~ main

   static int solve(int src, int dest) {

      boolean[] visited = new boolean[N];

      Queue<Integer> queue = new LinkedList<>();

      queue.add(src);

      while (!queue.isEmpty()) {

         int u = queue.poll();
         visited[u] = true;

         if (map[u][dest] == 1) return 1;

         for (int i = 0; i < N; i++) {

            if (map[u][i] == 1 && !visited[i]) {

               queue.add(i);
            }
         }
      }

      return 0;
   }
}

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%2311403_BFS_FindPath