백준 Java 11403 경로 찾기

문제

방향 그래프에서 경로를 구하고, 경로가 있다면 1을 표시하는 문제이다.

접근

bfs을 따라 가면서 나온 정점들의 간선들을 모두 기록을 하면 될 것 같다고 생각했다.
아주 간단하게 생각하면 모든 정점마다 탐색을 돌리고 그 값을 배열에 저장을 하면 될 것 같았다.
이때 중복해서 탐색이 발생하는 구간이 있었기 때문에, 이 부분에서 dp를 활용하면 더 최적화해서 풀 수 있지 않을까? 고민을 했지만 일단 첫번째 접근으로 풀어보고 실패하면 두번째 방법을 사용해서 풀어보려 했다.

---

구현

인접행렬이 주어져서 이를 활용해서 풀어도 되지만, 평소 인접 리스트를 활용해서 푸는 것을 좋아해 인접 리스트를 사용해서 문제를 풀었다.

사용 변수

int[][] answerArray; // 정답을 기록할 배열
List<LinkedList<Integer>> adj; // 인접 리스트

그래프 탐색

모든 정점에서 bfs를 활용해서 경로를 탐색하였다.
그리고 탐색 중 발견되는 정점들에 대해서 정답 배열에 표시를 해주었다.
탐색이 완료되면 배열 값을 출력하도록 하였다.

public void bfs(List<LinkedList<Integer>> adj){  
    for (int i = 0; i < adj.size(); i++) {  
        boolean[] visited = new boolean[adj.size()];  
         Queue<Integer> q = new LinkedList<>();  
         q.add(i);  
         visited[i] = true;  
        while (!q.isEmpty()) {  
            Integer poll = q.poll();  
  
            for(Integer integer : adj.get(poll)){  
                answerArray[i][integer] = 1;  
                if(!visited[integer]){  
                    visited[integer] = true;  
                    q.add(integer);  
  
                }  
            }  
        }  
    }  
}

결과

시간도 그렇게 오래걸리지 않고 맞추어서 다행인듯 싶다. 하지만 실제 코딩테스트에선 결과를 체크할 수 없는 상황이니 혹여나 DP를 사용해야 하는 상황이었다면 틀렸을 수 있겠다.

그래도 이 문제의 경우 N이 100이기 때문에 N*(N+E)가 발생해도 크게 문제되지는 않았나보다.

---

전체 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.Queue;  
import java.util.StringTokenizer;  
  
/*  
    https://www.acmicpc.net/problem/11403  
    그래프 탐색 실버 1  
 */public class P11403 {  
  
    int[][] answerArray;  
    List<LinkedList<Integer>> adj;  
    public void solution() throws Exception{  
        inputAndSetVariable();  
        bfs(adj);  
        printAnswer();  
    }  
  
    private void inputAndSetVariable() throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int n = Integer.parseInt(br.readLine());  
        answerArray = new int[n][n];  
        adj = new ArrayList<>();  
        for(int i = 0; i<n; i++)  
            adj.add(new LinkedList<>());  
        for(int i = 0; i<n; i++){  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int j = 0;  
            while (st.hasMoreTokens()) {  
                int k = Integer.parseInt(st.nextToken());  
                if (k == 1) {  
                    adj.get(i).add(j);  
                }  
                j++;  
            }  
        }  
    }  
  
    private void printAnswer() {  
        StringBuilder sb = new StringBuilder();  
        for (int[] arr : answerArray) {  
            for (int k : arr) {  
                sb.append(k).append(" ");  
            }  
            sb.append("\n");  
        }  
        System.out.println(sb);  
    }  
  
    public void bfs(List<LinkedList<Integer>> adj){  
        for (int i = 0; i < adj.size(); i++) {  
            boolean[] visited = new boolean[adj.size()];  
             Queue<Integer> q = new LinkedList<>();  
             q.add(i);  
             visited[i] = true;  
            while (!q.isEmpty()) {  
                Integer poll = q.poll();  
  
                for(Integer integer : adj.get(poll)){  
                    answerArray[i][integer] = 1;  
                    if(!visited[integer]){  
                        visited[integer] = true;  
                        q.add(integer);  
  
                    }  
                }  
            }  
        }  
    }  
  
    public static void main(String[] args) throws Exception {  
        new P11403().solution();  
    }  
  
}