이번에 알려드릴 알고리즘은 2차원배열을 이용한 "친한 짝 찾기 알고리즘" 입니다.
그것이 무엇이냐하면 예를 들면
학생들이
"철수" , "영희" , "바둑이" , "홍길동" , "허균" , "이름" , "생각" , "마린" , "개강" 이렇게 9명있고,
그중 친한 애들은 ("철수","영희") , ("바둑이", "홍길동") , ("생각", "철수") , ("개강","홍길동") 이렇게 있다면,
친한 짝들로 2명씩 묶으면
("철수","영희") | ("바둑이", "홍길동")
("철수","영희") | ("생각", "철수")
("철수","영희") | ("개강","홍길동")
("바둑이", "홍길동") | ("생각", "철수")
이렇게 4쌍이 나오게 됩니다.
//예외를 하자면 친한 애들이 한쌍이라면 이들은 서로 친구이기 때문에 경우의 수는 1이 됩니다.
네 그럼 바로 출력화면을 보겠습니다.
친한 짝들을 0 , 1 , 2 , 3 ... 이런식으로 표시했습니다. 참고바랍니다.
그럼 소스를 보도록 하겠습니다.
package blog;
import java.util.Scanner;
public class blogClass {
static boolean firend_Arr[][];
static int testCase[];
static int count =0;
public static void main(String [] args)
{
System.out.println("http://jsieun73.tistory.com/");
Scanner scanner = new Scanner(System.in);
System.out.println("몇번을 출력하시겠습니까?");
int Counting = scanner.nextInt();
testCase = new int[Counting];
for(int i=0; i<Counting; i++)
{
count = 0;
System.out.println("학생수, 친한짝 ");
int _Size = scanner.nextInt();
firend_Arr = new boolean[_Size][_Size];
int _CSize = scanner.nextInt();
//친한친구가 한명뿐일때 예외.
if(_CSize == 1)
{
count ++;
}
for(int j=0; j<_CSize; j++)
{
int first = scanner.nextInt();
int second = scanner.nextInt();
firend_Arr[first][second] = true;
}
NotCouple(_Size);
Couple(_Size);
testCase[i] = count;
}
//출력
for(int i=0; i<testCase.length; i++)
{
System.out.println((i + 1)+"번답 : " + testCase[i]);
}
}
static void NotCouple(int _Size)
{
for(int i=0; i<_Size; i++)
{
for(int j=0; j<_Size; j++)
{
if(firend_Arr[i][j]){}
else{
firend_Arr[i][j] = false;
}
}
}
}
static void Couple(int _Size)
{
for(int i=0; i< _Size; i++)
{
for(int j=0; j<_Size; j++)
{
if(firend_Arr[i][j])
{
if(check_Couple(i,j,_Size))
{
count++;
}
}
}
}
}
static boolean check_Couple(int _first , int _second,int _Size){
for(int i=0; i< _Size; i++)
{
for(int j=0; j< _Size; j++)
{
if(i != _first && i != _second && j != _first && j != _second && firend_Arr[i][j])
{
firend_Arr[i][j] = false;
firend_Arr[_first][_second] = false;
return true;
}
}
}
return false;
}
}
그럼 천천히 소스를 해석하도록 하겠습니다.
1. 메인 함수 그냥 값들을 입력하는거 뿐 그렇게 중요하진 않습니다.
2. NotCouple 메소드 중요도 ☆☆☆☆★
그렇게 중요하진 않지만, 꼭 필요한 메소드인거 같습니다.
설명을 하자면 친한 짝들을 제외한 배열들을 싹다 false 처리 했습니다.
3. Couple 메소드 중요도 ☆☆☆★★
이 메소드는 check_Couple 메소드를 실행시키기위한 메소드입니다.
간단히 설명하자면, firend_Arr 배열중에 true 인(친한짝)값들중 Check_Couple 메소드로 넘겨버리는 메소드입니다.
4. check_Couple 메소드 중요도 ☆★★★★
가장 중요하다고 생각되는 메소드입니다.
처음 친한 짝(_first,_Second )와 또다른 친한 짝을 찾는 메소드입니다.
그리고 그 친한 짝을 찾으면 리턴값을 줘서 다시 Couple 메소드에서 count 의 값이 카운팅 됩니다.
추가적으로 이미 한번 친한 짝들을 찾으면 그값들은 false 를 둬서 "중복방지" 를 했습니다.
문제 설명자체가 이해가 잘안되는 부분이 있는데요 (저도 문제풀때 이해를 못했습니다. 하지만, 입력과 출력화면을 보고 이해했다는..)
그럼 도움 되셨길 바랍니다. 포스팅을 마치도록 하겠습니다.
