[백준] 1260. DFS와 BFS

---

문제

 

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

1260번: DFS와 BFS

 

 

 같은 그래프를 DFS와 BFS로 출력하는 문제. 깊이우선탐색과 너비우선탐색의 기본을 다질 수 있는 문제다.

 

---

전략

 

01. Node 클래스 

 그래프의 노드 데이터들을 담을 Node 클래스를 생성한 뒤에 DFS와 BFS를 수행하는 방법. Node 클래스에는 정점 번호 데이터, 해당 노드와 연결된 노드, 방문 여부에 대한 정보가 들어가면 된다. 그럼 해당 노드를 방문하려고 할 때, 이미 방문했는지 체크가 가능하며 해당 노드와 연결된 노드들이 어떤 건지 확인 가능하다. 다만, 간선 데이터들이 오름차순이 아니므로 해당 노드와 연결된 노드들을 오름차순으로 정렬하는 과정이 필요하다.

 

 

02. 2차원 배열

 Node 클래스를 만들고 간선을 연결하고 매번 정렬하는 비용이 부담스럽다면 그냥 2차원 배열에 간선 정보를 저장하고 맨 앞에 0부터 N까지 읽어가면 따로 정렬할 필요가 없어진다. 직관적으로 이해하기는 어렵지만 더 빠르고 메모리도 적게 차지하는 방법이다.

 

---

풀이

 

Java

풀이 1 : Node 클래스

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

public class Main {

    static int N, M, V;
    static Node[] nodes;
    
    static class Node {
        int data;
        boolean visited = false;
        List<Node> children = new ArrayList<>();

        public Node(int data) {
            this.data = data;
        }

        public void add(Node node) {
            children.add(node);
            sort();
        }

        private void sort() {
            children.sort(Comparator.comparing(children -> children.data));
        }

        @Override
        public String toString() {
            return String.valueOf(data);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = info[0];
        M = info[1];
        V = info[2];
        nodes = new Node[N + 1];

        for (int i = 1; i < N + 1; i++) {
            nodes[i] = new Node(i);
        }

        for (int i = 0; i < M; i++) {
            int[] info2 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            nodes[info2[0]].add(nodes[info2[1]]);
            nodes[info2[1]].add(nodes[info2[0]]);
        }

        DFS(V);
        System.out.println();
        reset();
        BFS(V);
    }

    private static void DFS(int nxt) {
        System.out.printf("%d ", nodes[nxt].data);
        nodes[nxt].visited = true;

        List<Node> children = nodes[nxt].children;

        for (int i = 0; i < children.size(); i++) {
            Node child = children.get(i);

            if (!child.visited) {
                DFS(child.data);
            }
        }
    }

    private static void BFS(int nxt) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(nodes[nxt]);

        while (!queue.isEmpty()) {
            Node nxtNode = queue.poll();

            if (nxtNode.visited) continue;

            System.out.printf("%d ", nxtNode.data);
            nxtNode.visited = true;

            for (int i = 0; i < nxtNode.children.size(); i++) {
                Node child = nxtNode.children.get(i);
                if (!child.visited) {
                    queue.add(child);
                }
            }
        }
    }

    private static void reset() {
        for (int i = 1; i < nodes.length; i++) {
            nodes[i].visited = false;
        }
    }
}

 

 멤버 변수로는 입력 정보인 N, M, V과 Node들을 모아서 저장한 nodes 배열을 선언한다.

 

 다음으로는 Node 클래스인데 간단하게 Node 정보인 data와 방문 여부인 visited, 그리고 간선으로 연결된 다른 노드들의 리스트인 children을 선언하고 간선 정보를 추가하는 add() 메서드, 노드 리스트를 정렬하는 sort() 메서드를 만들어 주고, Node 객체 출력 시 data 정보만을 출력하기 위해 toString() 메서드를 오버라이드해주었다.

 

 이제 메인 메서드에서 입력 데이터를 받아 nodes 배열의 길이를 설정하고 길이만큼의 노드를 만들어 준 뒤, 간선 정보를 입력해주었다.

 

 이제 DFS(), BFS() 메서드를 각각 실행해 결과를 얻으면 된다. 이 때 두 메서드 사이에 reset() 메서드가 사용되었는데, DFS() 메서드가 실행하고 난 뒤, 노드 객체들의 방문 여부인 visited를 다시 false로 리셋시켜 주기 위함이다.

 

 DFS()는 깊이우선탐색을 가장 쉽게 구현할 수 있는 재귀를 이용했고, BFS()는 큐를 이용했다.

 

풀이2 : 2차원 배열 (다른 사람의 풀이)

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

public class Main {
	static int N, M, V;
	static int[][] arr;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();
	static Queue<Integer> q = new LinkedList<>(); 

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1][N+1];
		visited = new boolean[N+1];
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
		dfs(V);
		sb.append("\n");
		visited = new boolean[N+1];
		bfs(V);
		
		System.out.println(sb);
	}
	
	public static void dfs(int n) {
		visited[n] = true;
		sb.append(n + " ");
		
		for (int i=0; i<=N; i++) {
			if(arr[n][i] == 1 && !visited[i]) {
				dfs(i);
			}
		}
	}
	
	public static void bfs(int n) {
		q.add(n);
		
		while(!q.isEmpty()) {
			int c = q.poll();
			if(visited[c]) {
				continue;
			}
			visited[c] = true;
			sb.append(c + " ");
			for(int i=0; i<=N; i++) {
				if(arr[c][i] == 1 && !visited[i]) {
					q.add(i);
				}
			}
		}
	}
}

 

 다른 사람이 풀이한 결과다. 속도가 약 2배 가량 빨랐는데, 정렬 과정이 생략됐기 때문인 것으로 보인다. 정렬 과정이 생략된 이유는 이차원 배열에 간선 정보를 입력하고 0부터 반복문을 돌리면 작은 순서대로 실행되기 때문이다.

 

Python

 

import sys
from collections import deque


class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.visited = False
        self.children = []

    def add(self, node):
        self.children.append(node)
        self.sort()

    def sort(self):
        self.children.sort(key=lambda x: x.data)

    def __repr__(self):
        return str(self.data)


def dfs(nodes, data):
    node = nodes[data]
    print(node.data, end=" ")
    node.visited = True

    for child in node.children:
        if (not child.visited):
            dfs(nodes, child.data)


def bfs(nodes, data):
    queue = deque()
    queue.append(data)

    while queue:
        data = queue.popleft()
        node = nodes[data]

        if node.visited:
            continue

        print(node.data, end=" ")
        node.visited = True

        for child in node.children:
            if not child.visited:
                queue.append(child.data)


def reset(nodes):
    for node in nodes:
        if (node == None):
            continue

        node.visited = False


N, M, K = map(int, sys.stdin.readline().rstrip().split())
nodes = []
nodes.append(None)

for i in range(1, N + 1):
    nodes.append(Node(i))

for _ in range(M):
    n1, n2 = map(int, sys.stdin.readline().rstrip().split())
    nodes[n1].add(nodes[n2])
    nodes[n2].add(nodes[n1])

dfs(nodes, K)
print()
reset(nodes)
bfs(nodes, K)

 

 

 파이썬도 Node 클래스를 작성하는 방법으로 풀었다.

 

 

Javascript (Nodejs)

 

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split(/\r?\n/);

let currentLine = 0;
function readLine() {
  return input[currentLine++];
}

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  graph[start]
    .sort((a, b) => a - b)
    .forEach((next) => {
      if (!visited.has(next)) {
        dfs(graph, next, visited);
      }
    });
  return visited;
}

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  while (queue.length > 0) {
    const vertex = queue.shift();
    if (!visited.has(vertex)) {
      visited.add(vertex);
      graph[vertex]
        .sort((a, b) => a - b)
        .forEach((next) => {
          if (!visited.has(next)) {
            queue.push(next);
          }
        });
    }
  }
  return visited;
}

const [N, M, V] = readLine().split(" ").map(Number);
const graph = Array.from({ length: N + 1 }, () => []);

for (let i = 0; i < M; i++) {
  const [n1, n2] = readLine().split(" ").map(Number);
  graph[n1].push(n2);
  graph[n2].push(n1);
}

const dfsResult = Array.from(dfs(graph, V));
const bfsResult = Array.from(bfs(graph, V));

console.log(dfsResult.join(" "));
console.log(bfsResult.join(" "));

 

 

 Nodejs의 풀이는 다음과 같다.