ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [BOJ] #13023 _ ABCDE
    Problem Solving/BOJ 2019. 7. 10. 22:23

    [ABCDE] https://www.acmicpc.net/problem/13023

     

    13023번: ABCDE

    문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

    www.acmicpc.net

    처음에는 문제를 이해하기 어려웠다.

     

    문제를 해석하면,

    그냥 ABCDE가 친구이면 된다 == 5명이상이 친구이면 1, 아니면 0을 출력한다.

     

    좀 더 이해하기 쉽게 예제를 가지고 풀이해보자면,

     

    [예제 2번]

    다음과 같은 입력은 아래의 그래프와 같이 관계를 표현할 수 있다.

     

    해당 그래프에서 친구를 맺을 수 있는 관계의 수는 4이고, 5명이 친구를 맺을 수 있다.

    왜냐하면, 아래의 그래프와 같이 한번에 이어질 수 있는 노드의 갯수가 5개이다.

    0 - 3 - 2 - 1 - 4

     

    개인적으로 문제를 이해하는데 어려움을 주었던 예제 3번으로도 확인해보면,

     

    [예제 3번]

    입력 값의 관계는 아래와 같은 그래프로 표현할 수 있다.

     

    해당 그래프는 어떻게 이어보려고 해도 최대의 친구 수는 3명이다.

    1 - 0 - 3

     

    따라서, 0이 출력된다.

     

    결과적으로, 노드는 한번만 거치고 이어지는 갯수가 5이면, 1을 출력하고 아니면 0을 출력하면 된다.

    해당 문제를 풀기위해 DFS를 사용하였다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <algorithm>
    
    int relation[2000][2000] = { 0, };
    int idx_count[2000] = { 0, };
    int dfs(int idx, int check[], int count);
    int main() {
    	int n, m, a, b;
    	int check[2000] = { 0, };
    
    	scanf("%d %d", &n, &m);
    	for (int i = 0; i < m; i++) { //Input data
    		scanf("%d %d", &a, &b);
    		relation[a][idx_count[a]++] = b;
    		relation[b][idx_count[b]++] = a;
    	}
    
    	for (int i = 0; i < n; i++) { //Use DFS and Print result
    		if (dfs(i, check, 0)) {
    			printf("1");
    			return 0;
    		}
    	}
    	printf("0");
    
    	return 0;
    }
    
    int dfs(int idx, int check[], int count) {
    	check[idx] = 1;
    	for (int i = 0; i < idx_count[idx]; i++) {
    		if (check[relation[idx][i]] != 1) {
    			if (count + 1 == 4) return 1;
    			if (dfs(relation[idx][i], check, count + 1)) return 1;
    		}
    	}
    	check[idx] = 0;
    	return 0;
    }

    'Problem Solving > BOJ' 카테고리의 다른 글

    [BOJ] #15686 _ 치킨 배달  (0) 2019.08.04
    [BOJ] #17140 _ 이차원 배열과 연산  (0) 2019.07.17
    [BOJ] #16236 _ 아기상어  (0) 2019.07.11
    [BOJ] #14502 _ 연구소  (0) 2019.07.03
    [BOJ] #2156 _ 포도주 시식  (0) 2019.07.03

    댓글

@Jo Grini's Blog