DQuads

Code

public class DQuads

{

    public int count(String[] flights) {

        int n = flights.length;

        int count=0;

        int[][] a = new int[n][n];

        for (int i=0; i < n; i++) {

            if(flights[i].length() == 0) continue;

            String[] s = flights[i].split(" ");

            for (int j=0; j < s.length; j++)

                a[i][Integer.parseInt(s[j])]++;

        }

        for (int i=0; i < n; i++) {

            for (int j=0; j < n; j++) {

                for (int k=0; k < n; k++) {

                    for (int l=0; l < n; l++) {

                        if(i==j || i==k || i==l || j==k || j==l || k==l) continue;

                        if(a[i][j]==0 || a[j][k]==0 || a[k][l]==0 || a[l][i]==0) continue;

                        if(a[i][k]>0 || a[k][i]>0 || a[j][l]>0 || a[l][j]>0) continue;

                        count += a[i][j]*a[j][k]*a[k][l]*a[l][i];

                    }

                }

            }

        }

        return count/4;

    }

}

Explanation

1번째 for문

각 요소에 있는 숫자를 인덱스에 넣고 1씩 증가시킨다.

2번째 for문

각 i,j,k,l 이 같거나 값이 0이거나 대각선 방향으로 서로 연결되 있으면 continue 된다.

모든 요소를 돌면서 서로 연결되어 있는 꼭지점을 찾아 count에 저장한다. 중복되는 요소들 있기 때문에 전부 곱해줘야 한다.

References

https://community.topcoder.com/stat?c=problem_solution&cr=114853&rd=4497&pm=1663