친구 찾기

 

  Ex)

 

<hide/>
import java.util.Scanner;
public class Friend {

	static int MAX_COUNT = 56;
	static int[][] g_nAdjMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int[] g_nVisitMatrix = new int[MAX_COUNT];
	static int g_EdgeCnt;
	static int g_StartVertax, g_FisishVertax, g_Flag = 0;
	static int change;
	
	public static void main(String[] args) {
		int V1, V2;
		char trash, ch1, ch2;
		Scanner scan = new Scanner(System.in);
		g_EdgeCnt = scan.nextInt();

		for(int i = 0; i < g_EdgeCnt; ++i) {
			ch1 = scan.next().charAt(0);
			ch2 = scan.next().charAt(0);
				
			int uV1= change(ch1);
			int uV2 = change(ch2);
			
			g_nAdjMatrix[uV1][uV2] = 1;	// ch1, ch2 연결되어 있다.
			g_nAdjMatrix[uV2][uV1] = 1;
	//		System.out.printf("x: %d, y: %d\n", uV1 , uV2);
		}
	
		char x = scan.next().charAt(0);
		char y = scan.next().charAt(0);
		g_StartVertax = change(x);
		g_FisishVertax = change(y);
		DFSmethod(g_StartVertax);
		
		if(0 == g_Flag) {
				System.out.println("none!");
		}
		/*
		for(int i = 0; i <= 51; ++i) {
			for(int j =0; j <= 51; ++j) {
				System.out.printf(g_nAdjMatrix[i][j] + " " );
			}
			System.out.println();
		}
		*/
	}	
	
	public static int change(char _ch) {
		if('A' <= _ch && _ch <= 'Z') return (int) (_ch - 'A');
		else return  (int) (_ch - 'a' + 26);	// 대문자Z 바로 뒤부터 'a'시작
	}

	public static void DFSmethod(int _CurrVertax) {
		
		g_nVisitMatrix[_CurrVertax] = 1;	// 방문 처리
		for(int i = 0; i < MAX_COUNT; ++i) {
			if(g_FisishVertax == _CurrVertax) {
				g_Flag  = 1;
				System.out.println("friend\n");
				break;
			}
			if(1 == g_nAdjMatrix[_CurrVertax][i] && 0 == g_nVisitMatrix[i] ){
				System.out.printf("%c -> %c\n", 26 < _CurrVertax ? _CurrVertax + 'a' - 26 : _CurrVertax + 'A' , 26 < i ? i + 'a' - 26 : i + 'A');
				DFSmethod(i);
			}
		}
	}
}

 

  Note)

  - 입출력

5
A B
a b
E c
b c
c D
A c