아직 멀었나봅니다 ㅡ.ㅡ;;
그래프 관련 문제는 아직....너무 머리가 아파용 ㅠㅠ 문제 나오면 휴리스틱이고 다익스트라고 뭐고 다 안드로메다로..ㅠ
SRM 429번 DIV2 1000P에서....일단 파싱하고 쭉 그래프 따라간 담에 만약 방문한 노드가 아닐 경우는
따라가서 방문하면서 곱해주는 방식으로 문제를 풀었는데요...
좀 쉽게 푸는 방법 없을까용 ㅡ.ㅡ;; 너무 머리가 아팠어요.;;
그리고 약분...gcd... 흙흙...ㅠㅠㅠ 이런거 빨리 구현하는 노하우나 그런것도 있으면 좀 알려주세요~~~
역시 문제는 맨 아래에!!!!
public class IngredientProportions {
public int[][] p;
public int[] getMasses(String[] pt) {
int sz = pt.length;
int[] ret = new int[sz+1];
p = new int[sz+1][sz+1];
// 파싱
for (int i = 0; i < sz; i++) {
String str = pt[i];
int m = str.charAt(1)-'0';
int t = str.charAt(8)-'0';
int a = str.charAt(13)-'0';
int b = str.charAt(15)-'0';
p[m][t] = a;
p[t][m] = b;
}
for (int i = 0; i < sz+1; i++) {
boolean[] visited = new boolean[sz+1];
for (int j = 0; j < sz+1; j++)
visited[j] = false;
visited[i] = true;
ret[i] = visit(visited, i);
}
return yb(ret);
}
public int visit(boolean[] v, int i) {
boolean changed = false;
int j = 1;
for (int k = 0; k < v.length; k++) {
if (!v[k] && p[i][k] > 0) {
changed = true;
v[k] = true;
j *= p[i][k] * visit(v, k);
}
}
if (changed) return j;
return 1;
}
public int gcd(int a, int b)

{

if( a == 0 ) return b;

while( b > 0 )

{

if( a > b ) a = a-b;

else b = b-a;

}

return a;

}

// 약분하기 ㅡ.ㅡ;
public int[] yb(int[] a) {
int gb = a[0];
for (int i = 1; i < a.length; i++) {
gb = gcd(gb, a[i]);
}
for (int i = 0; i < a.length; i++) {
a[i] /= gb;
}
return a;
}
}
<출처 : TopCoder SRM>

{"#0 and #1 as 6:4"}                      

{"#0 and #1 as 9:8","#1 and #2 as 9:8"}                      

{"#4 and #0 as 1:1", "#4 and #1 as 3:1", "#4 and #2 as 5:1", "#4 and #3 as 7:1"}                      

{"#2 and #3 as 6:8", "#0 and #1 as 9:3", "#3 and #0 as 7:5"}