[백준] 11403 경로 찾기 - Java

 

 

 

문제 출저

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

11403번: 경로 찾기

 

 

 

문제 풀이

i,j로 가는데 갈 수 있으면 1, 갈 수 없으면 0으로 2차원 배열이 주어집니다.

이 때, i에서 j로 갈 수 있으면 1, 갈 수 없으면 0으로 표시하는 2차원 배열을 구해야 합니다. 

 

BFS로 풀었습니다. 

시작점을 매개변수로 받으면 다른 정점으로 갈 수 있는지 구하는 함수를 만들었습니다.

탐색은 BFS를 이용하였고 방문한 곳을 1차원 boolean 배열 visited로 표현해 중복 방문을 방지했습니다. 

정점 0부터 n까지 탐색하여 정답을 구했습니다.

 

 

 

소스 코드

package baekjoon.backjoon10.day1120.day12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


/*
경로 찾기
https://www.acmicpc.net/problem/11403
 */
public class B11403 {

    static int n;
    static int[][] board;
    static int[][] answer;
    static boolean[] visited;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        StringTokenizer st = null;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        answer = new int[n][n];

        for(int i = 0; i < n; i++) {
            search(i);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                sb.append(answer[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);

    }

    public static void search(int start) {
        visited = new boolean[n+1];

        Queue<Integer> que = new LinkedList<>();
        que.add(start);

        while (!que.isEmpty()) {
            Integer dot = que.poll();

            for(int i = 0; i < n; i++) {
                if(board[dot][i] == 1 && visited[i] == false) {
                    visited[i] = true;
                    answer[start][i] = 1;
                    que.add(i);
                }
            }
        }


    }

}