PostAddsense


UndergroundVault Topcoder



1
import java.util.ArrayList;

public class UndergroundVault
{
    int n;

    boolean canBeSealed(int[][] adj, boolean[] sealed, int room) {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i==room || k==room) continue;
                    if (adj[i][j] > adj[i][k] + adj[k][j])
                        adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }

        for (int i = 0; i < n; i++)
            if (!sealed[i] && adj[0][i]==1000000)
                return false;

        return true;
    }

    public int[] sealOrder(String[] rooms) {
        n = rooms.length;
        int[][] adj = new int[n][n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                adj[i][j] = 1000000;
        
        for (int i = 0; i < n; i++) {
            adj[i][i] = 1;

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

            String[] next = rooms[i].split(",");
            for (int j = 0; j < next.length; j++)
                adj[i][Integer.parseInt(next[j])] = 1;
        }

        boolean[] sealed = new boolean[n];
        ArrayList<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (sealed[j]) continue;

                int[][] temp1 = new int[n][n];
                int[][] temp2 = new int[n][n];
                for (int k = 0; k < n; k++)
                for (int l = 0; l < n; l++)
                    temp1[k][l] = temp2[k][l] = adj[k][l];

                for (int k = 0; k < n; k++)
                    temp1[j][k] = temp2[j][k] = 1000000;

                if (canBeSealed(temp2,sealed,j)) {
                    sealed[j] = true;
                    adj = temp1;
                    ret.add(j);
                    break;
                }
            }
        }

        ret.add(0);

        int[] ra = new int[ret.size()];
        for (int i = 0; i < ra.length; i++)
            ra[i] = ret.get(i);

        return ra;
    }
}

2
public class UndergroundVault
{
    int n;
    int cnt;
    boolean[][] d;
    boolean[] visit;
    boolean[] seal;

    void explore(int i) {
        if(seal[i] || visit[i]) return;
        cnt++;
        visit[i] = true;

        for (int j=0; j < n; j++)
            if(d[i][j]) explore(j);
    }

    public int[] sealOrder(String[] rooms) {
        n = rooms.length;
        d = new boolean[n][n];
        visit = new boolean[n];
        seal = new boolean[n];

        for (int i=0; i < n; i++) {
            String[] x = rooms[i].split(",");

            for (String s : x)
                if(!s.equals("")) d[i][Integer.parseInt(s)] = true;
        }

        int[] sol = new int[n];

        for (int i=0; i < n; i++) {
            int maxi = -1;
            int max = -1;

            for (int j=0; j < n; j++) {
                if (!seal[j]) {
                    visit = new boolean[n];
                    seal[j] = true;

                    cnt=0;
                    explore(0);
                    if(cnt > max) {max = cnt; maxi = j;}

                    seal[j] = false;
                }
            }

            seal[maxi] = true;
            sol[i] = maxi;
        }

        return sol;
    }
}


Explanation

1
플로이드 워셜 알고리즘을 사용한다. adj배열에서 1000000은 경로가 없음을 1은 경로가 있음을 나타낸다. 주 함수의 반복문에서 사전순으로 방을 봉인하기 위해 0부터 n까지의 순서를 사용한다. j번 방을 봉인하고 canBeSealed() 함수를 통해 다른 경로로 j번 방을 들어갈 수 있는지 플로이드 워셜 알고리즘을 이용해 알아낸다. !sealed[i] && adj[0][i]==1000000 조건을 만족하면 j번 방으로 들어갈 수 있는 다른 경로가 없다는 뜻이므로 false를 반환하고 그렇지 않으면 true를 반환한다.

2
j 반복문에서 방 하나만 seal하고 explore를 통해 방문 횟수(cnt)가 가장 많은 방 번호를 찾아 maxi에 저장한다. j반복문이 끝나면 maxi번호 방을 seal하고 sol 배열에 maxi 번호를 저장한다.

0번 방부터 시작하므로 길이가 같을 경우, 굳이 비교하지 않아도 된다. (놀랍다..)

입력 {"1,2,3", "4,5,6", "5,6,8", "8", "5,6", "7,9", "11", "3", "11", "7,10", "4", ""}의 그림.
(한 번호씩 차례로 소거해보면 답을 쉽게 찾을 수 있다.)


References