글 읽기 - dfs와 인접행렬을 이용해서 풀이했습니다.

seonjoo2030 5년 전 0

우선, 정점의 갯수만큼 행과 열을 만들고, 그리고 입력받은 노드를 인접행렬로 생성했습니다.

그리고 정점의 숫자 만큼 for문을 돌려서 체크하도록 했고,

dfs를 수행하며 하나의 배열에다 인접한 요소의 숫자를 하나씩 저장하도록 했습니다.

예를 들어, 1 2 5가 연결된 노드라면,

res[0]에 1을 넣고, 그 다음 2, 그 다음 5를 넣어서 최종적으로는 res[0]에 0이 아닌 숫자가 저장되도록 했습니다.

그리고 res 배열에 0이 아닌 값이 들어갈 경우 count값을 하나 증가시켜 다음 인접 요소를 저장하도록 했습니다.

결과적으로 count 값을 출력함으로써 인접요소의 갯수를 출력하도록 했습니다.

그런데 무엇이 잘못되었는지 잘 모르겠습니다. ㅜㅜ

#include <iostream>
#include <cstdio>

int N, M, u, v, map[1001][1001], visit[1001], res[500000]; //인접행렬 map, 방문노드 확인 visit, 인접요소 갯수 확인 res
int count;// 인접요소의 갯수
void dfs(int start);//dfs

int main()
{
	scanf("%d %d", &N, &M);  // 노드와 간선 갯수 입력
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &u, &v);  // 인접행렬 생성
		map[u][v] = 1;
		map[v][u] = 1;
	}
	for (int i = 1; i <= N; i++)  // 1행부터 N행 까지 검사
	{
		dfs(i);
		if (i > 0 && res[count] != 0)  // 전에 있는 res 값이 0이 아닌 경우, 즉 인접요소가 있으면  count 증가
			count++;
	}
	printf("%d\n", count);
}

void dfs(int start)
{
	visit[start] = 1;  //방문함 체크

	for (int i = 1; i <= N; i++)
	{
		if (map[start][i] == 1 && visit[i] == 0)
		{
			dfs(i);
			res[count] = i;
		}
	}
}

djm03178 5년 전 1

인접한 정점이 없어도 하나의 연결 요소가 될 수 있습니다.

1 0 의 정답은 1입니다.

seonjoo2030 5년 전 0

아하! 제가 count를 체크하는 부분을 생각하지 못한것이 있었네요 ㅜㅜ

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs와 인접행렬을 이용해서 풀이했습니다.

seonjoo2030 5년 전 0

djm03178 5년 전 1

seonjoo2030 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말