BFS 구현하기 (백준 24444번)

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

이번엔 DFS의 짝꿍 BFS
저번 DFS에서 ArrayList<ArrayList<Integer>>를 사용했어서 이번에는 배열을 시도했다.

package BOJ.BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_24444 {

    static int visited[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 정점의 수
        int M = Integer.parseInt(st.nextToken());
        ; // 간선의 수
        int R = Integer.parseInt(st.nextToken());
        ; // 시작 정점

        visited = new int[N + 1]; // 정점 수 +1 만큼 (1~N이라서) 방문 여부 배열
        boolean arr[][] = new boolean[N + 1][N + 1];

        for (int i = 0; i <= N; i++) { // N+1개의 정점 생성 (0 때문)

        } // 0~N 까지 생성

        for (int i = 0; i < M; i++) { // 간선 입력 받는 부분
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st2.nextToken());
            int end = Integer.parseInt(st2.nextToken());

            arr[start][end] = true;
            arr[end][start] = true;
            // 방향이 없는 무방향 간선이기 때문에 양쪽으로 이어준다.
        }

        bfs(R,arr);

        for(int i=1;i<=N;i++){
            sb.append(visited[i]).append("\n");
        }
        System.out.println(sb);

    }


    // 시작 정점을 Queue에 넣는다.
    // 반복문
    // index = queue.remove();
    // index와 접한 정점을 Queue에 넣는다
    // Queue가 빌때까지 반복
    // 반복문

    public static void bfs(int start, boolean arr[][]){
        Queue<Integer> queue = new LinkedList<>();
        int seq = 1;
        queue.add(start);
        int index = 0;

        while(!queue.isEmpty()){
            index = queue.remove();
            if(visited[index] !=0) continue;
            visited[index] = seq++;


            for(int i =0;i<arr[index].length;i++){
                if(arr[index][i] == true && visited[i] == 0){ // 연결 되어 있고 아직 방문하지 않은 정점이면 Queue에 집어 넣는다.
                    queue.add(i);
                }
            }

        }



    }
}

1%에서 메모리 초과가 떠버렸다.
아무래도 10만 단위의 데이터라서 감당을 못하는 거 같아서 List를 기로 했다.

package BOJ.BFS;

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

//ArrayList<ArrayList<Integer>>  사용하기
public class BOJ_24444_2 {

    static int visited[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 정점의 수
        int M = Integer.parseInt(st.nextToken());
        ; // 간선의 수
        int R = Integer.parseInt(st.nextToken());
        ; // 시작 정점

        visited = new int[N + 1]; // 정점 수 +1 만큼 (1~N이라서) 방문 여부 배열
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for (int i = 0; i <= N; i++) { // N+1개의 정점 생성 (0 때문)
            graph.add(new ArrayList<>());
        } // 0~N 까지 생성

        for (int i = 0; i < M; i++) { // 간선 입력 받는 부분
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st2.nextToken());
            int end = Integer.parseInt(st2.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
            // 방향이 없는 무방향 간선이기 때문에 양쪽으로 이어준다.
        }
        for(int i=1;i<=N;i++){
            Collections.sort(graph.get(i)); // 오름차순 정렬해주기 BFS는 Queue를 사용하기 때문에 정렬하고자하는 차순과 같게 정렬한다.
        }

        bfs(R,graph);

        for(int i=1;i<=N;i++){
            sb.append(visited[i]).append("\n");
        }
        System.out.println(sb);

    }


    // 시작 정점을 Queue에 넣는다.
    // 반복문
    // index = queue.remove();
    // index와 접한 정점을 Queue에 넣는다
    // Queue가 빌때까지 반복
    // 반복문

    public static void bfs(int start, ArrayList<ArrayList<Integer>> graph){
        Queue<Integer> queue = new LinkedList<>();
        int seq = 1;
        queue.add(start);
        int index = 0;

        int node = 0;

        while(!queue.isEmpty()){
            index = queue.remove();
            if(visited[index] !=0) continue;
            visited[index] = seq++;


            for(int i =0;i<graph.get(index).size();i++){
                node = graph.get(index).get(i);
                if(visited[node] == 0){ // 연결 되어 있고 아직 방문하지 않은 정점이면 Queue에 집어 넣는다.
                    queue.add(node);
                }
            }

        }



    }
}

DFS BFS는 2차원 ArrayList로 만드는 게 나을 것 같다.
가장 기본적인 DFS BFS를 이제서야 하게되다니