백준 1260번: DFS와 BFS

문제

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

1260번: DFS와 BFS

---

풀이

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 깊이우선탐색과 너비우선탐색의 개념을 익히는 문제입니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] list;
    static StringBuilder sb = new StringBuilder();

    public static void dfs(int value) {
        visited[value] = true;
        sb.append(value).append(" "); // (2)
        if (list[value] != null) {
            for (int e : list[value]) {
                if (!visited[e]) {
                    dfs(e); // (3)
                }
            }
        }
    }

    public static void bfs(int value) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(value); // (4)
        visited[value] = true;
        while (!queue.isEmpty()) {
            int p = queue.poll();
            sb.append(p).append(" "); // (5)
            if (list[p] != null) {
                for (int e : list[p]) {
                    if (!visited[e]) {
                        queue.offer(e); // (6)
                        visited[e] = true;
                    }
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    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());
        visited = new boolean[n + 1];
        list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        for (int i = 1; i <= n; i++) {
            if (list[i] != null) {
                Collections.sort(list[i]); // (1)
            }
        }
        dfs(v);
        sb.append("\n");
        Arrays.fill(visited, false);
        bfs(v);
        System.out.print(sb);
    }
}

임의의 수 x가 있을 때 ArrayList 배열 list[x]는 x번 정점에 연결된 정점들을 의미합니다.

 

(1) 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야하기 때문에 모든 list 배열들을 정렬합니다.

자바 util 패키지의 Collections 클래스의 sort() 메서드를 이용하여 정렬했습니다.

이 문제에서 dfs 함수의 깊이는 중요하지 않기 때문에 매개변수로 정점의 번호를 의미하는 value 한 개만 사용합니다.

 

(2) value번 정점의 방문여부 visited[value]를 true로 초기화한 후에 Stringbuilder sb에 해당 값을 넣어줍니다.

이후 value번 정점에 연결된 정점이 있는지 확인합니다.

 

(3) 연결된 정점이 1개라도 있다면(list[value] != null) foreach문을 통해서 value번 정점에 연결된 정점(e번 정점들)의 방문여부를 확인합니다.

방문한 적이 없다면 dfs(e)로 함수를 재귀적으로 실행하며 sb에 값을 넣어줍니다.

dfs 함수가 끝난 후에 visited 배열의 모든 값을 false로 초기화해준 뒤에 bfs 함수를 실행합니다.

 

(4) 먼저 탐색을 시작할 정점의 번호 value를 큐에 삽입하고 value번 정점의 방문여부 visited[value]를 true로 초기화합니다.

이후 큐가 비어있지 않을 때까지 (5) ~ (6)번 과정을 반복합니다.

 

(5) 큐에서 poll한 값을 p라고 했을 때 sb에 p를 추가한 후에 p번 정점에 연결된 정점이 있는지 확인합니다.

연결된 정점이 1개라도 있다면(list[p] != null) foreach문을 통해서 마찬가지로 p번 정점에 연결된 정점(e번 정점들)의 방문여부를 확인합니다.

 

(6) 방문한 적이 없다면 큐에 e를 삽입하고 e번 정점을 방문처리합니다.

모든 과정이 끝나면 sb를 출력한 후에 프로그램을 종료합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int arr[1001][1001], cnt[1001] = { 0 }, *visited;
typedef struct node {
	int x;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int x) {
	node* now = (node*)malloc(sizeof(node));
	now->x = x;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
int pop(Queue* queue) {
	int re;
	node* now;
	now = queue->front;
	re = now->x;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
int compare(const void* a, const void* b) {
	int o1 = *(int*)a;
	int o2 = *(int*)b;
	if (o1 > o2) return 1;
	else if (o1 < o2) return -1;
	else return 0;
}
void dfs(int value) {
	printf("%d ", value);
	visited[value] = 1;
	for (int i = 0; i < cnt[value]; i++) {
		if (!visited[arr[value][i]]) {
			dfs(arr[value][i]);
		}
	}
}
void bfs(int value) {
	Queue queue;
	initQueue(&queue);
	push(&queue, value);
	visited[value] = 1;
	while (!empty(&queue)) {
		int tmp = pop(&queue);
		for (int i = 0; i < cnt[tmp]; i++) {
			if (!visited[arr[tmp][i]]) {
				push(&queue, arr[tmp][i]);
				visited[arr[tmp][i]] = 1;
			}
		}
		printf("%d ", tmp);
	}
}
main() {
	int n, m, v;
	scanf("%d %d %d", &n, &m, &v);
	visited = (int*)malloc(sizeof(int) * (n + 1));
	memset(visited, 0, sizeof(int) * (n + 1));
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		arr[x][cnt[x]++] = y;
		arr[y][cnt[y]++] = x;
	}
	for (int i = 1; i <= n; i++) {
		qsort(arr[i], cnt[i], sizeof(int), compare);
	}
	dfs(v);
	printf("\n");
	memset(visited, 0, sizeof(int) * (n + 1));
	bfs(v);
}

자바를 이용한 풀이와 동일합니다. Stringbuilder에 넣어두었다가 한꺼번에 출력하는 방법 대신 바로바로 출력하며 ArrayList 배열은 보다 빠른 정렬을 위해 연결리스트가 아닌 2차원 배열을 이용하여 구현했습니다.

---

결론

깊이우선탐색 dfs와 너비우선탐색 bfs의 기초를 다질 수 있는 문제였습니다. 또한 이번 문제부터 코드 해석 글을 작성하는 방식을 좀 바꾸기로 했습니다. 기존의 글자의 색을 다르게 표현한 글은 가독성이 떨어지는 것 같다는 피드백을 받았기 때문입니다. 더 좋은 방식을 알게 된다면 즉각 반영하여 앞으로 더 좋은 글을 작성할 수 있도록 노력하겠습니다.