[BAEKJOON_11403 - JAVA] 경로 찾기

 

해결 과정

인접행렬을 뽑아내는 문제로 기존의 풀었던 문제들과 비슷했지만 어렵게 생각해 오래 걸렸던 문제.
기본적인 bfs에 각 행과 열에 대한 반복문을 씌워 문제를 해결.

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
    static int N;
    static int[][] map;
    static int[][] result;
    static void bfs() {
        for (int i = 0; i < N; i++) {
            Queue<Integer> q = new LinkedList<>();
            boolean visited[] = new boolean[N];
            q.offer(i); // 행 단위 검사
            while (!q.isEmpty()) {
                int x = q.poll();
                for (int j = 0; j < N; j++) { // 열단위 검사
                    if (map[x][j] == 1 && !visited[j]) { // 간선이 존재하는 경우 && 방문 여부
                        q.offer(j);
                        visited[j] = true;
                        result[i][j] = 1;
                    }
                }
            }
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        result = new int[N][N];
        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());
            }
        }
        // ============================ 입력 =============================
        bfs();
        // 출력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}

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

11403번: 경로 찾기