백준 11724번 DFS 탐색에서 궁금한 부분이 있습니다.

백준 11724번
Ctrl+F 여기가 궁금
백준 11724번은
그래프 문제인데
연결요소의 갯수(그래프뭉치?) 를 찾는 문제입니다.

그래프를 인접리스트표현으로 구현해서
DFS 탐색을 할 때 graph 클래스의 2차원 벡터 adjList 로
정점과 간선을 표현했는데

왜 그 정점과 연결된 간선의 갯수가 0보다 클 때 DFS 를 하려고 하면
백준에서 틀렸다고 합니다.

무향 그래프라서 adjList에 넣을 땐 최소 1 이상의 adjList[i].size() 가 나오니까
내가 입력하지 않은 수는 쓸데없이 DFS하지 않으려고 했는데
그 부분이 문제가 된건데 왜 문제가 되는건지 모르겠습니다.

요약: 인접리스트 그래프에 DFS 탐색조건을
리스트의 크기 > 0 으로 하면 백준에서 틀렸다고 하는 이유를 모르겠음.


class Graph {
public:
	std::vector<std::vector<int>> adjList;
	std::vector<int> visited;
	int vertexCnt;
	int edgeCnt;
	Graph(int vertex, int edge) {
		vertexCnt = vertex;
		adjList.resize(vertex+1);
		visited.resize(vertex+1,false);
		edgeCnt = edge;
	}	//생성자 

	void vertexConnect(const int a,const int b) {
		adjList[a].push_back(b);
	}

	void DFS(const int vertex) {
		visited[vertex] = true;
			for (int &nextVertex : adjList[vertex]) {
//			printf("vertex:%d --> %d",vertex, list);		
				if (visitedCheck(nextVertex))	//이 위치가 방문하지 않았다면
				{
	//				printf("\t true\n");
					DFS(nextVertex);
				}
			}		
	}
	bool visitedCheck(const int &next){
		if (!visited[next]) {	//방문을 안했으면 false 		
			return true;
		}
		return false;	}

};

Graph graphMake(bool flag) {
	int vertex;
	int edge;
	std::cin >> vertex >> edge;
	if (flag)	//true 는 인접리스트 
	{
		return Graph(vertex, edge);
	}
	else
	{
		printf("인접행렬은 아직 안만들었음.\n");
		exit(1);//인접행렬 아직안만듬
	}
}
	int main(void)
{		
		Graph graph = graphMake(true); //true는 인접리스트, false는 인접행렬
//		printf("%d",graph.edgeCnt);
		for(int i=0;i < graph.edgeCnt; ++i){
			int a, b;
			std::cin >> a >> b;
			graph.vertexConnect(a, b);
			graph.vertexConnect(b, a); //무향
		}		

		int graphCnt = 0;

//		printf("VertexCnt:%d\n", graph.vertexCnt);
		for (int i = 1; i <= graph.vertexCnt; ++i) {
//			int edgeSize = graph.adjList[i].size();
//			printf("%d -> edgeSize:%d\n",i, edgeSize);
//			if(edgeSize > 0) {	//사이즈가 1 이상일 경우 여기가 궁금
				if (graph.visitedCheck(i)) {
					++graphCnt;
					graph.DFS(i);
				}
//			}		//사이즈 검사를 하면 백준에서 틀렸다고 한다.
		}

		printf("%d\n", graphCnt);
		return 0;
}

자바 하다 오셨나봐요? ㅎㅎ

이런 글 올리실 때는 링크도 가져와 주세요.

https://www.acmicpc.net/problem/11724
깜빡했네요 ; 본문에도 추가했어요
C -> java -> C++ 단계로 공부했습니다.
자바때 했던 단일 책임 원칙이 생각나서 저렇게 나누게 되네요

우선 naive한 dfs 풀이입니다.

#include <iostream>
#include <vector>

auto main() -> int {
    int N, M, ans = 0;
    std::vector< std::vector< int > > data;
    std::vector< int > ch;

    std::cin >> N >> M;
    data.resize(N + 1);
    ch  .resize(N + 1);

    for (int i = 0; i < M; ++i) {
        int t1, t2; std::cin >> t1 >> t2;
        data[ t1 ].push_back(t2);
        data[ t2 ].push_back(t1);
    }

    for (int i = 1; i <= N; ++i) {
        if (ch[ i ]) continue;

        std::vector< int > v = { i };

        ch[ i ] = 1;
        ++ans;

        while(!v.empty()) {
            int t1 = v.back(); v.pop_back();

            for (auto j: data[ t1 ])
                if (!ch[ j ])
                    ch[ j ] = 1, v.push_back(j);
        }
    }

    std::cout << ans;
    return 0;
}

벡터의 벡터에 연결 정보를 담습니다. 물어보신 부분은 이 코드와 비교해 보시면 될 것 같습니다.


다음은 유니온 파인드 풀이입니다. 실행 시간 줄이느라 std::cin 대신 scanf를 사용했습니다.

#include <cstdio>

int v[ 1024 ] = { 0 };

auto rec(int x) -> int {
    if (v[ x ] != x)
        v[ x ] = rec(v[ x ]);
    return v[ x ];
}

auto main() -> int {
    int N, M; scanf("%d %d", &N, &M);

    for (int i = 1; i <= N; ++i)
        v[ i ] = i;

    for (int i = 0; i < M; ++i) {
        int t1, t2; scanf("%d %d", &t1, &t2);
        t1 = rec(t1); t2 = rec(t2);

        if (t1 == t2) continue;
        v[ t1 ] = t2;
        if (--N == 1) break;
    }

    printf("%d", N);
    return 0;
}
3 Likes

결국 경우는 데이터의 크기가 0이지만 DFS로 최소한 자기 자신을 TRUE로 바꿔야 한단 건가보네요.
근데 그 이유를 아직 못 깨달았습니다…

어느 정점과도 연결되지 않은 정점 역시 별개의 연결 요소이기 때문입니다 :hugs:

1 Like