정보올림피아드 초등 _ 지역본선 2014. 4번문제 저울

안녕하세요!

오늘은  정올 초등 2014년에  지역본선으로 나왔던 4번문제  '저울'을  풀어보았습니다.

codeup.kr/problem.php?id=4805

저울

처음엔  물건 비교결과를 어떤식으로 나열해야할지  감이 안와서 고민해봤는데,

"물건 비교결과를 알수없는 갯수"를  출력해야한다는 문장을 보고선   그래프 형태로 표현하고  탐색할 수 있냐 없냐갖고 따지면  쉽게 풀릴거같단 느낌이 와서   그래프로 표현하게 되었습니다.

 위 사진처럼 연결관계그래프라는걸 사용했고

 

문제 해결 소스와  문제풀이과정 영상 첨부하겠습니다!

 

정보올림피아드 초등을 대비하고있는 학생들에게    도움되었으면 좋겠네요 ㅎㅎ

#include <stdio.h>


void findTargetCount(int target, int *cnt, int graphs[][101], int n, int visited[])
{
	visited[target] = 1;
		
//	printf("findTargetCount(%d,%d)\n",target,*cnt);
	for(int i=1;i<=n;i++)
	{
		if(graphs[target][i] == 1 && visited[i] == 0){
			*cnt = *cnt + 1;
			findTargetCount(i,cnt,graphs,n, visited);
		}
	}
}


void findTargetToCount(int target, int *cnt, int graphs[][101], int n, int visited[])
{
	visited[target] = 1;
		
//	printf("findTargetToCount(%d,%d)\n",target,*cnt);
	for(int i=1;i<=n;i++)
	{
		if(graphs[i][target] == 1 && visited[i] == 0){
			*cnt = *cnt + 1;
			findTargetToCount(i,cnt,graphs,n,visited);
		}
	}
}		
		
int main()
{
	int n;
	scanf("%d",&n);
	
	int m;
	scanf("%d",&m);
	
	int graphs[101][101] ={};
	
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		
		//graphs[x][y] = graps[y][x] = 1;
		graphs[x][y] = 1;
	}

	//2. 자신한테 연결된방향 숫자 갯수
	// + 자신 + 
	//자신이 가리키는쪽으로 쭉 갯수 (dfs)


	for(int target=1;target<=n;target++){
		int cnt=1;
		int visited[101] = {};
		
	//	printf("target %d \n",target);
		//자신한테 연결된방향 숫자 갯수
		
		findTargetCount(target,&cnt, graphs,n, visited);
		
		//자신이 가리키는쪽으로 쭉 갯수
		findTargetToCount(target,&cnt, graphs,n, visited);
		 
		
		printf("%d\n",n-cnt);
	}

	
		
		
		
		
	return 0;
}