<java> 백준 18352 - bfs, 그래프 탐색

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

18352번: 특정 거리의 도시 찾기

 

그래프를 입력하고 bfs로 탐색하는 가장 기초적인 문제이다

 

list = new ArrayList[node+1];
for(int i = 0; i< list.length; i++){
    list[i] = new ArrayList<>();
}

for(int i = 0; i< edge; i++){
    str = reader.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    list[a].add(b);
}

인접리스트로 그래프를 저장해준다

 

visit =  new int[node+1];
Arrays.fill(visit, -1);

방문 리스트를 만들어주고 -1로 채워준다(방문하지 않은 상태)

 

static void bfs(int node) {
    Queue<Integer> Q = new LinkedList<>();
    Q.add(node);
    visit[node]++;
    while(!Q.isEmpty()){
        int now = Q.poll();
        for(int i : list[now]){
            if(visit[i] == -1) {
                visit[i] = visit[now]+1;
                Q.add(i);
            }
        }
    }
}

탐색 경로를 만들어주고(Queue 생성)

 

첫 방문지점을 탐색 경로에 더해준다

 

해당 지점에서 갈 수 있는 지점 하나하나에 대해

만약 이전에 방문하지 않은 지점 일때는 방문 리스트에 현재 거리에 +1을 저장한다

 

후에 출발할 지점으로 탐색 경로에 저장!

 

 

 

간단해 보이지만 이해하는데에 많은 시간이 걸렸다.

 

<전체 code>

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

public class Q18352 {
    static int[] visit;
    static List<Integer>[] list;
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] str = reader.readLine().split(" ");
        int node = Integer.parseInt(str[0]);
        int edge = Integer.parseInt(str[1]);
        int distance = Integer.parseInt(str[2]);
        int start = Integer.parseInt(str[3]);


        list = new ArrayList[node+1];
        for(int i = 0; i< list.length; i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i< edge; i++){
            str = reader.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            list[a].add(b);
        }

        visit =  new int[node+1];
        Arrays.fill(visit, -1);

        bfs(start);


        int count = 0;
        for(int i = 0; i< node+1; i++){
            if(visit[i] == distance){
                writer.write(i+"\n");
                count++;
            }
        }

        if(count == 0){
            System.out.println(-1);
        }else{
            writer.flush();
        }


    }
    static void bfs(int node) {
        Queue<Integer> Q = new LinkedList<>();
        Q.add(node);
        visit[node]++;
        while(!Q.isEmpty()){
            int now = Q.poll();
            for(int i : list[now]){
                if(visit[i] == -1) {
                    visit[i] = visit[now]+1;
                    Q.add(i);
                }
            }
        }
    }
}