백준 16940번: BFS 스페셜 저지

문제

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

16940번: BFS 스페셜 저지

 

---

풀이

정점에 1부터 n까지 번호가 매겨져 있는 양방향 그래프를 표현한 트리가 있을 때 어떤 수열이 BFS 알고리즘을 이용했을  때 해당 수열의 순서대로 방문할 수 있는지 확인하는 문제입니다. 이때 정점을 방문하는 순서는 중요하지 않습니다.

---

접근

BFS, DFS 알고리즘은 정점끼리 어떤 순서로 연결돼있는지에 따라 방문 순서가 달라집니다.

하지만 이 문제에서는 방문 방문가 먼저 나온 뒤에 이 순서대로 출력이 가능한지 확인해야 합니다.

그래서 저는 정점에 연결된 다른 정점들을 ArrayList 배열인 list로 표현했고 list[모든 정점 번호]를 주어진 수열의 순서대로 정렬한 뒤에 bfs 함수를 실행했습니다.

 

---

코드

자바

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

public class Main {

    static int n;
    static int[] arr;
    static boolean[] visited;
    static ArrayList<Integer>[] list;

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        int cnt = 0;
        while (!queue.isEmpty()) { // (3)
            int p = queue.poll();
            if (p != arr[cnt++]) { // (4)
                System.out.println(0);
                System.exit(0);
            }
            visited[p] = true;
            if (list[p] != null) { // (5)
                for (int e : list[p]) {
                    if (!visited[e]) {
                        queue.offer(e);
                        visited[e] = true;
                    }
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        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 < n - 1; i++) {
            StringTokenizer 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);
        }
        arr = new int[n];
        int[] order = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) { // (1)
            arr[i] = Integer.parseInt(st.nextToken());
            order[arr[i]] = i;
        }
        for (int i = 1; i <= n; i++) {
            if (list[i] != null) { // (2)
                Collections.sort(list[i], new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return order[o1] - order[o2];
                    }
                });
            }
        }
        bfs();
        System.out.println(1); // (6)
    }
}

(1) 그래프를 표현할 트리의 입력이 끝나면 i를 포함한 for문 안에서 수열을 순서대로 입력합니다.

이때 수열을 입력한 순서도 order[arr[i]] = i를 통해 기록해둡니다.

 

(2) 이후 i를 포함한 for문 안에서 각 정점에 연결된 다른 정점들을 수열의 순서를 기준으로 정렬합니다.

예를 들어 수열이 1 3 2 4이고 1번 정점에 순서대로 2번 정점과 3번 정점을 연결시켰다면 3번 정점보다 2번 정점을 먼저 탐색할 수 있도록 위치를 변경하는 것입니다.

이때 ArrayList를 정렬하기 위해서 Collections 클래스의 sort 메서드를 이용했는데 Comparator 객체를 compare 메서드를 수정하여 Collections.sort 메서드의 추가 인자로 사용하여 기존의 정렬 기준을 바꿨습니다.

 

모든 입력이 끝나면 bfs 함수로 들어갑니다.

 

(3) 큐에 탐색 시작 정점 번호인 1을 삽입한 뒤에 큐가 비어있지 않을 때까지 다음 과정을 반복합니다.

이때 수열이 담긴 arr 배열을 차례대로 비교해보기 위한 정수 cnt를 0으로 초기화합니다.

 

(4) 큐에서 poll한 정수를 p라고 했을 때 p가 arr[cnt++]와 다르다면 0을 출력한 뒤에 프로그램을 종료합니다.

(2)번 과정에서 수열의 순서를 기준으로 정렬했기 때문에 값이 서로 다르다면 실패입니다.

 

(5) p번 정점의 방문처리를 진행한 후에 p번 정점에 연결된 다른 정점이 있는지 확인합니다.

다른 정점이 있으면 foreach문을 통해 연결된 정점(e번 정점)들을 확인합니다.

e번 정점에 방문한 적이 없다면 방문처리를 해준 뒤에 큐에 삽입합니다.

 

(6) bfs 함수가 끝난 후에는 1을 출력한 후에 프로그램을 종료합니다.

(4)번 과정에서 프로그램이 종료되지 않았다면 문제 조건을 만족한 것이기 때문입니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n, *arr, *visited, *order;
typedef struct node {
	int data;
	struct node* next;
} node;
void add(node* target, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = target->next;
	target->next = now;
	return;
}
node* list[100001];
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 data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	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;
	if (queue->count == 0) {
		return -1;
	}
	now = queue->front;
	re = now->data;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	push(&queue, 1);
	int cnt = 0;
	while (!empty(&queue)) {
		int p = pop(&queue);
		if (p != arr[cnt++]) {
			printf("0");
			exit(0);
		}
		visited[p] = 1;
		node* curr = list[p]->next;
		while (curr != NULL) {
			if (!visited[curr->data]) {
				push(&queue, curr->data);
				visited[curr->data] = 1;
			}
			curr = curr->next;
		}
	}

}
int compare(const void* a, const void* b) {
	int o1 = *(int*)a;
	int o2 = *(int*)b;
	return order[o1] - order[o2];
}
main() {
	scanf("%d", &n);
	visited = (int*)malloc(sizeof(int) * (n + 1));
	memset(visited, 0, sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		list[i] = (node*)malloc(sizeof(node));
		list[i]->next = NULL;
	}
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		add(list[x], y);
		add(list[y], x);
	}
	arr = (int*)malloc(sizeof(int) * n);
	order = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		order[arr[i]] = i;
	}
	int* sorted = (int*)malloc(sizeof(int) * n);
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		node* curr = list[i]->next;
		while (curr != NULL) {
			sorted[cnt++] = curr->data;
			node* prev = curr;
			curr = curr->next;
			free(prev);
		}
		list[i]->next = NULL;
		qsort(sorted, cnt, sizeof(int), compare);
		while (cnt) {
			add(list[i], sorted[--cnt]);
		}
	}
	bfs();
	printf("1");
}

자바를 이용한 풀이와 동일합니다. ArrayList 배열은 연결리스트를 이용하여 구현했습니다.

또한 각 정점에 연결된 다른 정점들의 순서를 정렬하기 위해 정수 배열 sorted를 따로 만들어 i를 포함한 for문에서 list[i]와 연결된 모든 값을 sorted에 넣은 후에 정렬하고 그 후에 list[i]에 순서대로 삽입했습니다.

 

---

결론

처음에 이 문제를 접근할 때 BFS 알고리즘을 사용했을 때 나올 수 있는 모든 경우의 수를 수열과 비교하려고 했는데 한눈에 봐도 너무 비효율적이라고 생각하여 위와 같은 방법을 생각해냈습니다.