[Java] 백준 11403 : 경로 찾기

문제 링크

1.

처음 문제를 보았을 때, 방향 그래프 인접 행렬이라는 점에서 조금 복잡하게 생각했다.

 

 

2.

자료구조 수업시간 때 인접 리스트 구성한 것을 떠올려 보면, 무방향 그래프에서 1에서 2로 가는 간선이 있다면 2에서 1로 가는 간선도 인접 리스트에 추가를 했었다. 방향 그래프라면 1에서 2로 가는 간선만 추가할 것이다.

 

이를 통해 그냥 배열을 순회하는 기본적인 BFS 문제와 다를 게 없다고 판단했다. 다만 사이클 생기는 부분을 주의해야 할 것이다.

 

$0$번째 행부터 $n-1$번째 행까지 각 행에 대하여 BFS 탐색을 한다.

 

 

3.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n;
    static int[][] arr;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        bfs();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }

    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 v = q.poll();

                for (int j = 0; j < n; j++) {
                    if (arr[v][j] == 1 && !visited[j]) {
                        visited[j] = true;
                        arr[i][j] = 1;
                        q.offer(j);
                    }
                }
            }
        }
    }
}

 

 

4.

인접 행렬과 인접 리스트의 차이

 

[참고] https://sarah950716.tistory.com/12