[C] 백준 - 24479번: 깊이 우선 탐색 1

5월 16일(화) - 그래프와 순회 (24479번)

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 기본적인 dfs 구조를 활용

- 배열 arr는 그 크기가 너무 커질 우려가 있으므로 malloc을 이용해서 2차원으로 크기설정

- compare 함수를 이용해서 qsort 진행

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. C언어로 풀이를 진행해보니, 어떤 방법으로 진행하더라도 메모리 초과가 발생하게된다

-> 일단 자바로 풀이

-> 추후에 C언어를 이용한 풀이도 모색

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

[C] 풀이 -> 메모리 초과

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int** arr;
int visited[100001];
int result[100001];
int N, M, R;
int count = 0;

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (*(int*)a > *(int*)b)
	{
		return 1;
	}
	else if (*(int*)a < *(int*)b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

void dfs(int start, int num)
{
	if (visited[start] == 1)
	{
		return;
	}

	visited[start] = 1;
	count++;
	result[start] = count;


	for (int i = 1; i <= num; i++)
	{
		if (arr[start][i] == 1 && visited[i] == 0)
		{
			dfs(i, num);
		}
	}
	return;
}

int main(void)
{
	scanf("%d %d %d", &N, &M, &R);

	arr = (int**)malloc(sizeof(int*) * N);
	for (int i = 0; i < N; i++)
	{
		arr[i] = (int*)malloc(sizeof(int) * N);
	}

	int from, to;
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &from, &to);
		arr[from][to] = 1;
		arr[to][from] = 1;
	}

	dfs(1, N);

	for (int i = 1; i <= N; i++)
	{
		printf("%d\n", result[i]);
	}
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

[Java] 풀이 -> 정답

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

import java.util.Collections;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] check;
    static int count;

    public static void main(String[] args) throws IOException{
        st = new StringTokenizer(br.readLine());

        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int startVertex = Integer.parseInt(st.nextToken());

        check = new int[vertex+1];

        for(int i=0; i<vertex+1; i++)
        {
            graph.add(new ArrayList<>());
        }

        for(int i=0; i<edge; i++)
        {
            st = new StringTokenizer(br.readLine());
            int frontVertex = Integer.parseInt(st.nextToken());
            int toVertex = Integer.parseInt(st.nextToken());

            graph.get(frontVertex).add(toVertex);
            graph.get(toVertex).add(frontVertex);
        }

        for(int i=1; i<graph.size(); i++)
        {
            Collections.sort(graph.get(i));
        }

        count=1;
        DFS(startVertex);

        for(int i=1; i<check.length; i++)
        {
            sb.append(check[i]).append("\n");
        }
        System.out.println(sb);
    }

    private static void DFS(int vertex){
        check[vertex] = count;

        for(int i=0; i<graph.get(vertex).size(); i++)
        {
            int newVertex = graph.get(vertex).get(i);

            if(check[newVertex] == 0)
            {
                count++;
                DFS(newVertex);
            }
        }
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ