백준11403_경로찾기

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 

3
0 1 0
0 0 1
1 0 0

예제 출력 

1 1 1
1 1 1
1 1 1

수업시간에 배운 인접리스트 방식으로 구현했다.

Linked 라는 클래스를 만들고, 그 안에 LinkedList 변수를 만들었다.

그리고 main 함수에는 Linked 배열변수를 선언했다. 

이 그림으로 설명해보자면 맨앞에있는 배열이 Linked 변수, 그리고 각 배열에 연결되어있는 것이 LinkedList 다!

[코드]

import java.util.Iterator;
import java.util.Scanner;
import java.util.LinkedList;
 
public class Main {
 
    public static int N;
    public static Linked L[];
    public static int check[][];
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점의 개수
        L = new Linked[N]; // 정점 개수 크기만큼 Linked 배열 만들기
        check = new int[N][N]; // 각 정점에서 다른 정점까지 도달할 수 있는지를 저장하는 배열
 
        for (int i = 0; i < N; i++)
            L[i] = new Linked();
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int v = sc.nextInt();
                if (v == 1) {
                    L[i].addNode(j); // 인접리스트에 추가해준다.
                }
            }
        }
 
         
        for (int i = 0; i < N; i++) {
            DFS(i, i);
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(check[i][j] + " ");
            }
            System.out.println();
        }
 
    }
 
    public static void DFS(int c, int s) {
        for (int i = 0; i < L[c].getSize(); i++) { // 현재 정점과 바로 이어져있는 정점수라고 보면 됌!
            int next = L[c].getNum(i);
            if (check[s][next] == 0) { // 값이 1인 애들은 방문할 수 있다는 뜻이니까 고려하지 않아도 됌
                check[s][next] = 1; // s 정점에서 next 정점에 방문할 수 있다는 뜻
                DFS(next, s); // 이제 next 정점과 이어진 다른 정점 탐색하러 가는 역할
            }
        }
    }
}
 
class Linked {
 
    LinkedList<Integer> L = new LinkedList<Integer>();
 
    public void addNode(Integer v) {
        L.add(v);
    }
 
    public int getNum(int i) {
        return L.get(i);
    }
 
    public int getSize() {
        return L.size();
    }
 
    public void printList() {
        for (Iterator<Integer> it = L.iterator(); it.hasNext();) {
            System.out.print(it.next() + " ");
        }
    }
 
}

[알고리즘]

1. 우선은 Linked 라는 클래스를 따로 만들어서 그 안에 클래스변수로 Integer 형 LinkedList 를 하나 만들어줬다.

2. main 함수에서 Linked 배열변수를 하나 만들어주었다. (정점 수만큼)

3. static 변수 check 는 i 에서 j 까지 가는 길이 있는지를 저장하는 변수이다.

4. DFS(c,s)는 s 정점에서 닿을 수 있는 정점을 체크해주는 함수! 정확히는 check[s][?]의 숫자를 정하는 역할이다. s 정점에서 시작해 다다를 수 있는 곳에 1을 저장해준다.

5. DFS 함수를 정점 수 만큼 호출해준다. ( 줄 32 )

6. check 변수의 값을 출력해준다.

더 간단히 할 수 있는 방법도 있을 것 같은데 ㅜ

다른 사람 코드도 좀 참고해봐야겠다!