[BOJ][JAVA] 1260 : DFS와 BFS

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

1260번: DFS와 BFS

---

    static int cnt = 0;
    // 망한 코드
    public static void dfs(int[][] map, boolean[] visited, int v){
        // v 행부터 보면 될 것.
        System.out.print(v+" ");
        int newV = 0;
        for(int i=0; i<map.length; i++){
            if(map[v][i] == 1 & !visited[i]){
                visited[i] = true;
                newV = i;
                cnt++;
                break;
            }
        }
        if(cnt != map.length){
            dfs(map, visited, newV);
        }
    }

오답노트(푸는 동안 사고과정 및 개선점)

BFS는 그래도 큐를 쓰면서 쉽게 구현했는데, DFS를 구현 할 때 재귀를 사용하는게 아직 어렵게 느껴진다. 반복으로 익숙해지는 수 밖에 없을 것 같다. 또 이번에 전역변수를 사용하기 시작했는데, 재귀를 쓰려면 전역변수를 쓰는 게 편하기도 하고, 함수로 빼낼 거면 인수로 넣는 방법말고 전역으로 선언해서 초기화만 잘 해주면 더 편하겠다는 생각이 들었다.

 

DFS는 계속 타고 타고 들어가고, BFS는 인접한 거 다 챙기면서 하나 뽑을 때 인접한 거 다 챙기고 넘어간다는 것만 기억하고 있으면 되겠다. DFS는 그래서 Stack으로도 구현 가능한데 다른 문제에서 한번 도전해봐야겠다.

---

정답코드

import java.sql.Array;
import java.util.*;
import java.io.*;

public class Main
{
    static int n, m, v;
    static int[][] map;
    static boolean[] visited; // 전역으로 쓰는 이유는 함수에서 다 갖다 쓰려고

    static void dfs(int node){
        visited[node] = true;
        System.out.print(node+" ");
        for(int i = 1; i <= n; i++){
            if (map[node][i]==1 & !visited[i]){
                dfs(i);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();

        Queue<Integer> q = new LinkedList<>();
        map = new int[n+1][n+1]; // 정점 개수 만큼 map
        visited = new boolean[n+1];

        // 인접행렬에 값 넣기, 무방향 그래프임.
        for(int i=0; i<m; i++){
            int src = sc.nextInt();
            int dst = sc.nextInt();
            map[src][dst] = 1;
            map[dst][src] = 1;
        }
        // DFS
        dfs(v);
        System.out.println();
        visited = new boolean[n+1]; // 방문 배열초기화하기
        // BFS
        q.offer(v);
        while(!q.isEmpty()){
            int node = q.poll();
            visited[node] = true;
            System.out.print(node+" ");
            for(int i=1; i<=n; i++){
                if(map[node][i] == 1 & !visited[i]){
                    q.offer(i);
                    visited[i] = true; // 넣으면서 방문처리를 해줘야 됨. 안하면 똑같은 정점이 중복으로 추가 됨
                }
            }
        }
    }
}

 

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^