[ 백준 - 11403 ] 경로 찾기

난이도 : S1

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

Tag : 그래프, BFS

 

문제 탐색하기 

- 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점에서 i에서 j로 가는 경로가 존재하는지 여부를 파악하는 문제입니다.

 

시도 1 ( 성공😲)

떠오른 문제 해결 방법

각 정점을 기준으로 bfs를 진행한뒤, 방문한 노드들은 경로가 존재하므로, 이를 바탕으로 출력하면 해결할 수 있다고 생각했습니다.

시간복잡도⏰

bfs시간복잡도 O( V + E)에 각 정점마다 이를 실행해야하므로 V * O( V + E).

노드의 총 개수 N (1 ≤ N ≤ 100).

간선의 최대 개수는 자신을 제외한 모든 노드에 간선이 있을 경우, 즉 99*99 = 9801 

100*9801 = 980,100 으로 시간내에 충분히 가능합니다.

 

구현 방법 

세부 구현 사항

1. 주어진 값을 입력받는다. 

2. 인접리스트로 그래프를 생성한다.

3. 모든 점을 시작점으로 하여 bfs를 통해 탐색한다.

4. 각 정점을 시작점으로 한 모든 노드의 방문 정보를 배열에 저장한다.

5. 방문 정보를 출력한다.

전체코드

import java.io.IOException;
import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            List<Integer> input = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                int isConnect = Integer.parseInt(st.nextToken());
                if (isConnect == 0)
                    continue;
                input.add(j);
            }
            graph.add(input);
        }

        int[][] answer = new int[n][n];
        for (int i = 0; i < n; i++) {
            int[] visited = new int[n];
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(i);
            while (!queue.isEmpty()) {
                int parent = queue.poll();
                List<Integer> childs = graph.get(parent);
                for (int child : childs) {
                    if (visited[child] != 0)
                        continue;
                    queue.add(child);
                    visited[child] = 1;
                }
            }
            answer[i] = visited;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bw.write(answer[i][j] + " ");
            }
            bw.newLine();
        }
        bw.flush();
    }
}

 

 

마무리

BFS, 그래프등은 단골 문제이므로 많이 연습하자.