[1260] DFS와 BFS

해당 문제는 DFS, BFS 둘 다 이용해서 풀어야 하는 문제이다.

🚨 특이점은 구현 시에 1. LinkedList를 사용하거나 2. 배열을 사용해서 풀거나
두 가지로 나뉘는데 이 문제는 배열 기준으로 채점기준이 되어있기 때문에 LinkedList를 사용해서 풀 때는 오름차순으로 값을 넣어줘야 한다. 그러면 채점 기준을 만족하며 풀 수 있다.

추가사항으로는, bfs 문제풀이 시에 큐에 넣을 때에 방문처리를 해줘야 한다는 점이다.
이때 방문 처리를 안 하면 이후 큐에 있는 것과 인접한 요소일 때 다시 큐로 들어와서 여러번 들어와 처리 잘못 될 수도 있다.

문제 링크👇🏻
백준 1260번

1. 배열 사용하여 graph 정의

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

class Graph{
    int n;
    int[][] graph;

    public Graph(int n){
        this.n=n;
        graph=new int[n+1][n+1];
    }

    void addEdge(int v, int w){
        graph[v][w]=1; graph[w][v]=1;
    }

    void dfs(int v){
        boolean [] visited=new boolean[n+1];

        dfsUtil(v, visited);
    }

    void dfsUtil(int v, boolean[] visited){
        System.out.print(v+" ");
        visited[v]=true;

        for(int i=0;i<n+1;i++){
            if (graph[v][i]==1 && !visited[i])
                dfsUtil(i,visited);
        }

    }

    void bfs(int v){
        boolean [] visited=new boolean[n+1];
        LinkedList<Integer> queue=new LinkedList();
        queue.addLast(v);
        visited[v]=true;
        System.out.print(v+" ");

        while(queue.size()!=0){
            int now=queue.poll();

            for(int i=0;i<n+1;i++){
                if(graph[now][i]==1 && !visited[i]){
                    visited[i]=true;
                    queue.add(i);
                    System.out.print(i+" ");
                }
            }
        }
    }
}

public class Main{
    public static void main(String[] args) throws Exception{
        //본격적 수행 하는 부분

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        int v=Integer.parseInt(st.nextToken());
        Graph graph=new Graph(n);

        for(int i=0;i<m;i++){
            StringTokenizer graphSt=new StringTokenizer(bf.readLine());
            int m1=Integer.parseInt(graphSt.nextToken());
            int m2=Integer.parseInt(graphSt.nextToken());
            graph.addEdge(m1, m2);
        }

        graph.dfs(v);
        System.out.println();
        graph.bfs(v);

    }
}

2. LinkedList 이용하여 graph 정의

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

class Graph{
    int n;
    LinkedList<Integer> graph[];

    public Graph(int n){
        this.n=n;
        graph=new LinkedList[n+1];
        for(int i=0;i<n+1;i++){
            graph[i]=new LinkedList();
        }
    }

    void addEdge(int v, int w){

        //차례대로 맞는 곳에 넣기
        LinkedList<Integer> tempDist=graph[v];

        int idx;
        for(idx=0;idx<tempDist.size();idx++){
            if(tempDist.get(idx)>w) break;
        }

        tempDist.add(idx,w);
    }

    void dfs(int v){
        boolean [] visited=new boolean[n+1];

        dfsUtil(v, visited);
    }

    void dfsUtil(int v, boolean[] visited){
        System.out.print(v+" ");
        visited[v]=true;
        Iterator<Integer> it=graph[v].listIterator();
        while(it.hasNext()){
            int n=it.next();

            if(!visited[n]){
                dfsUtil(n,visited);
            }
        }
    }

    void bfs(int v){
        boolean [] visited=new boolean[n+1];
        LinkedList<Integer> queue=new LinkedList();
        queue.addLast(v);

        while(queue.size()!=0){
            int n=queue.poll();
            
            if (!visited[n]) {
                visited[n] = true;
                System.out.print(n + " ");
            }
            
            Iterator<Integer> it=graph[n].listIterator();

            while(it.hasNext()){
                int gn=it.next();

                if(!visited[gn]){
                    queue.add(gn);
                }

            }

        }

        //queue
        Iterator<Integer> qit=queue.listIterator();
        while(qit.hasNext()){
            int qn=qit.next();
            System.out.print(v+" ");
            visited[qn]=true;

            Iterator<Integer> it=graph[qn].listIterator();
            while(it.hasNext()){
                int n=it.next();
                if(!visited[n])
                    queue.addLast(n);
            }
        }
    }
}

public class Main{
    public static void main(String[] args) throws Exception{
        //본격적 수행 하는 부분

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        int v=Integer.parseInt(st.nextToken());
        Graph graph=new Graph(n);

        for(int i=0;i<m;i++){
            StringTokenizer graphSt=new StringTokenizer(bf.readLine());
            int m1=Integer.parseInt(graphSt.nextToken());
            int m2=Integer.parseInt(graphSt.nextToken());
            graph.addEdge(m1, m2);
            graph.addEdge(m2, m1);
        }

        graph.dfs(v);
        System.out.println();
        graph.bfs(v);

    }
}