[백준 | Java Silver II ] (#1260) DFS와 BFS

문제

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

---

이슈

☝️연결된 정점을 저장하는 List를 정렬해줘야 두번째 테스트케이스 통과! 

☝️메모리 초과 - ArrayList 대신 LinkedList로 사용해야 제출 성공! 

---

첫번째 코드 - 메모리 초과 (실패)

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

public class Main {
    static boolean[] visited;
    public static void dfs(int N, Map<Integer, ArrayList<Integer>> list, int V) {
        //방문 처리
        visited[V] = true;
        System.out.print(V + " ");

        ArrayList<Integer> al = list.get(V);
        Collections.sort(al);
        for (int i = 0; i < al.size(); i++) {
            //연결된 정점을 탐색하면서 방문하지 않은 곳을 탐색
            if(!visited[al.get(i)]) {
                dfs(N, list, al.get(i));
            }
        }
    }

    public static void bfs(int N, Map<Integer, ArrayList<Integer>> list, int V){
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(V);

        while(!q.isEmpty()){
            int n = q.poll();
            //인접한 정점들을 다 큐에 넣어준다
            ArrayList<Integer> al = list.get(n);
            Collections.sort(al);
            for (int i = 0; i < al.size(); i++) {
                q.add(al.get(i));
            }

            //큐에서 하나씩 꺼내면서 방문하지 않은 정점은 방문처리
            if(!visited[n]){
                visited[n] = true;
                System.out.print(n + " ");
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        //정점 별로 초기화
        Map<Integer, ArrayList<Integer>> list = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            list.put(i, new ArrayList<>());
        }

        //간선들 list에 양방향으로 추가해주기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }

        visited = new boolean[N+1];
        dfs(N, list, V);
        System.out.println();

        visited = new boolean[N+1];
        bfs(N, list, V);
    }
}

 

수정된 코드 -  ArrayList 대신 LinkedList를 사용, 중복 연산 제거 (성공)

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

public class Main {
    static boolean[] visited;

    public static void dfs(int V, Map<Integer, List<Integer>> list) {
        visited[V] = true;
        System.out.print(V + " ");

        List<Integer> al = list.get(V);
        for (int i = 0; i < al.size(); i++) {
            if (!visited[al.get(i)]) {
                dfs(al.get(i), list);
            }
        }
    }

    public static void bfs(int V, Map<Integer, List<Integer>> list) {
        Queue<Integer> q = new LinkedList<>();
        q.add(V);
        visited[V] = true;

        while (!q.isEmpty()) {
            int n = q.poll();
            System.out.print(n + " ");

            List<Integer> al = list.get(n);
            for (int i = 0; i < al.size(); i++) {
                if (!visited[al.get(i)]) {
                    visited[al.get(i)] = true;
                    q.add(al.get(i));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        Map<Integer, List<Integer>> list = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            list.put(i, new LinkedList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }

        // 정점 리스트 정렬
        for (int key : list.keySet()) {
            Collections.sort(list.get(key));
        }

        visited = new boolean[N + 1];
        dfs(V, list);
        System.out.println();

        visited = new boolean[N + 1];
        bfs(V, list);
    }
}

 

최종 코드 - BufferedWriter 추가

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

public class Main {
    static boolean[] visited;
    static BufferedWriter bw;

    public static void dfs(int V, Map<Integer, List<Integer>> list) throws IOException {
        visited[V] = true;
        bw.write(V + " ");

        List<Integer> al = list.get(V);
        for (int i = 0; i < al.size(); i++) {
            if (!visited[al.get(i)]) {
                dfs(al.get(i), list);
            }
        }
    }

    public static void bfs(int V, Map<Integer, List<Integer>> list) throws IOException {
        Queue<Integer> q = new LinkedList<>();
        q.add(V);
        visited[V] = true;

        while (!q.isEmpty()) {
            int n = q.poll();
            bw.write(n + " ");

            List<Integer> al = list.get(n);
            for (int i = 0; i < al.size(); i++) {
                if (!visited[al.get(i)]) {
                    visited[al.get(i)] = true;
                    q.add(al.get(i));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        Map<Integer, List<Integer>> list = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            list.put(i, new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.get(s).add(e);
            list.get(e).add(s);
        }

        // 정점 리스트 정렬
        for (int key : list.keySet()) {
            Collections.sort(list.get(key));
        }

        visited = new boolean[N + 1];
        dfs(V, list);
        bw.newLine();

        visited = new boolean[N + 1];
        bfs(V, list);

        bw.flush();
        bw.close();
        br.close();
    }
}