[알고리즘 / 백준] 1260 - DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제는 위와 같으며 DFS 와 BFS 를 구현할 수 있다면 간단하게 해결할 수 있습니다. 여기서 주의할 점은 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다"는 것입니다.

 

먼저 DFS 는 방문이 필요한 노드를 담을 stack 과 이미 방문한 노드를 담을 queue 가 있으면 구현할 수 있고, BFS 는 방문이 필요한 노드를 담을 queue 와 이미 방문한 노드를 담을 queue 가 있으면 구현할 수 있습니다.

 

예제를 간략하게 테이블 형태로 살펴보면 다음과 같습니다.

 

주어진 노드들을 그래프 형태로 만들기 위해 파이썬에서는 dictionary 형태에 list 를 값으로 담도록 하였고, 자바에서는 HashMap 에 값으로 ArrayList 를 담도록 하여 서로 연결된 노드들을 표현하였습니다.

 

ex) {key_노드1 : [key_노드1에서_갈_수_있는_노드1, key_노드1에서_갈_수_있는_노드2,key_노드1에서_갈_수_있는_노드3, ...], key_노드2: [key_노드2에서_갈_수_있는_노드1, ...], ...}

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


def dfs(node_list, start_node):
    need_visit = list()
    visited = list()

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            if node in node_list:
                need_visit.extend(sorted(node_list[node], reverse=True))  # 작은 수부터 뒤에서 pop 할 수 있도록 역정렬 후 삽입

    return visited


def bfs(node_list, start_node):
    need_visit = list()
    visited = list()

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            if node in node_list:
                need_visit.extend(sorted(node_list[node]))  # 작은 수부터 앞에서 pop 할 수 있도록 정렬 후 삽입

    return visited


n, m, v = map(int, stdin.readline().split())
nodes = dict()

for _ in range(m):
    n1, n2 = map(int, stdin.readline().split())
    if n1 in nodes:
        nodes[n1].append(n2)
    else:
        nodes[n1] = [n2]

    if n2 in nodes:
        nodes[n2].append(n1)
    else:
        nodes[n2] = [n1]

result = " ".join(map(str, dfs(nodes, v)))
result += "\n"
result += " ".join(map(str, bfs(nodes, v)))

print(result)

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int[] nmv = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Map<Integer, ArrayList> nodes = new HashMap<>();
        for (int i = 0; i < nmv[1]; i++) {
            int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            if (nodes.containsKey(nums[0])) {
                nodes.get(nums[0]).add(nums[1]);
            } else {
                nodes.put(nums[0], new ArrayList(Arrays.asList(nums[1])));
            }

            if (nodes.containsKey(nums[1])) {
                nodes.get(nums[1]).add(nums[0]);
            } else {
                nodes.put(nums[1], new ArrayList(Arrays.asList(nums[0])));
            }
        }

        for (Integer v : dfs(nodes, nmv[2])) {
            sb.append(v).append(" ");
        }

        sb.append("\n");

        for (Integer v : bfs(nodes, nmv[2])) {
            sb.append(v).append(" ");
        }

        System.out.println(sb);
    }

    private static ArrayList<Integer> dfs(Map<Integer, ArrayList> nodeList, int startNode) {
        ArrayList<Integer> needVisit = new ArrayList<>();
        ArrayList<Integer> visited = new ArrayList<>();

        needVisit.add(startNode);
        while (!needVisit.isEmpty()) {
            int node = needVisit.remove(needVisit.size() - 1);
            if (!visited.contains(node)) {
                visited.add(node);
                if (nodeList.containsKey(node)) {
                    Collections.sort(nodeList.get(node));
                    Collections.reverse(nodeList.get(node));
                    needVisit.addAll(nodeList.get(node));
                }
            }
        }

        return visited;
    }

    private static ArrayList<Integer> bfs(Map<Integer, ArrayList> nodeList, int startNode) {
        ArrayList<Integer> needVisit = new ArrayList<>();
        ArrayList<Integer> visited = new ArrayList<>();

        needVisit.add(startNode);
        while (!needVisit.isEmpty()) {
            int node = needVisit.remove(0);
            if (!visited.contains(node)) {
                visited.add(node);
                if (nodeList.containsKey(node)) {
                    Collections.sort(nodeList.get(node));
                    needVisit.addAll(nodeList.get(node));
                }
            }
        }

        return visited;
    }
}