백준 13023번: ABCDE

문제

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

13023번: ABCDE

---

풀이

0번부터 N-1번으로 번호가 매겨진 사람들 중에 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 확인하는 문제입니다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] list;

    public static void dfs(int dpth, int idx) {
        if (dpth == 4) { // (4)
            System.out.println(1);
            System.exit(0);
        }
        visited[idx] = true;
        if (list[idx] != null) { // (2)
            for (int e : list[idx]) {
                if (!visited[e]) {
                    dfs(dpth + 1, e); // (3)
                }
            }
        }
        visited[idx] = false;
    }

    @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());
        visited = new boolean[n];
        list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        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 = 0; i < n; i++) { // (1)
            dfs(0, i);
        }
        System.out.println(0);
    }
}

임의의 수 x가 있을 때 ArrayList 배열 list[x]는 x번 사람과 친구사이인 사람들을 의미합니다.

dfs 함수에서 dpth는 깊이, 즉 연결된 친구 관계의 수이며 idx는 현재 확인 중인 사람의 번호입니다.

 

(1) 모든 입력이 완료되면 i를 포함한 for문 안에서 dfs(0, i)를 실행합니다.

for문이 끝나면 문제 조건에 맞는 ABCDE가 존재하지 않는다는 뜻이므로 0을 출력하고 프로그램을 종료합니다.

 

(2) idx번 사람의 방문여부 visited[idx]를 true로 초기화한 후에 idx번 사람의 친구관계의 존재 여부를 확인합니다.

친구관계가 있다면(list[idx] != null) foreach문을 통해서 idx번 사람의 친구(e번 사람)의 방문 여부를 확인합니다.

 

(3) 방문한 적이 없다면 dfs(dpth + 1, e)로 함수를 재귀적으로 실행합니다.

foreach문이 종료되면 idx번 사람의 방문여부 visited[idx]를 false로 초기화해준 다음에 함수를 반환합니다.

 

(4) dpth가 4가 되면 친구관계가 4개, 즉 A <=> B <=> C <=> D <=> E가 완성됐다는 뜻이므로 1을 출력합니다.

이후 0이 또 출력되지 않도록 System.exit(0)을 통해 프로그램을 종료합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
int* visited;
typedef struct node {
	int x;
	struct node* next;
} node;
void add(node* target, int x) {
	node* now = (node*)malloc(sizeof(node));
	now->x = x;
	now->next = target->next;
	target->next = now;
	return;
}
node* list[2000];
void dfs(int dpth, int idx) {
	if (dpth == 4) {
		printf("1");
		exit(0);
	}
	visited[idx] = 1;
	node* curr = list[idx]->next;
	while (curr != NULL) {
		if (!visited[curr->x]) {
			dfs(dpth + 1, curr->x);
		}
		curr = curr->next;
	}
	visited[idx] = 0;
}
main() {
	int n, m;
	scanf("%d %d", &n, &m);
	visited = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		list[i] = (node*)malloc(sizeof(node));
		list[i]->next = NULL;
		visited[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		add(list[x], y);
		add(list[y], x);
	}
	for (int i = 0; i < n; i++) {
		dfs(0, i);
	}
	printf("0");
}

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

---

결론

탐색 순서가 정해져있지 않고 문제 조건에 맞는 경우를 찾을 수 있는지만 출력하면 되는 문제였기 때문에 dfs의 개념을 이해하고 있다면 누구든 해결하기 어렵지 않았을 것이라고 생각합니다.