알고리즘(등굣길, 순위)

[등굣길]

 

* 조건

1. m과 n이 주어진다
2. 집의 위치(1,1)에서 목적지(m,n)까지 갈 수 있는 최단경로의 개수를 구한다
3. puddles[][]는 홍수로 인해 지나갈 수 없는 좌표를 뜻한다

 

 

* 알고리즘

• DP

 

 

* 로직

• 배열 사이즈를 map[n+1][m+1]로 설정해둔다
• 집(1,1)을 중심으로 피라미드 형태로 값을 더해가면 목적지까지 갈 수 있는 최소 경로의 경우의 수를 구할 수 있다
• 배열 전체를 돌 때, 만약 현재 좌표의 값이 0이면서
  • 위의 좌표 값이 갈 수 없는 길이라면 -> 현재 좌표의 값 = 현재 좌표의 왼쪽 값 + 0
  • 왼쪽 좌표 값이 갈 수 없는 길이라면 -> 현재 좌표의 값 = 현재 좌표의 위쪽 값 + 0
  • 둘다 갈 수 있는 길이라면 -> 현재 좌표의 값 = 위쪽 값 + 왼쪽 값
• 도착지 좌표의 값이 0보다 크지 않다면 0개를 출력하고, 크다면 해당 값을 출력한다

 

public class Problem_Tortoise {

    public static void main(String[] args) {
        int m = 4;  //열
        int n = 3;  //행
        int[][] puddles = {
                {2, 2}
        };

        int answer = solution(m, n, puddles);
        System.out.println(answer);
    }

    public static int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] dp = new int[n+1][m+1];

        //map의 시작점 셋팅
        dp[1][1] = 1;

        //map의 장애물 셋팅
        for(int[] puddle : puddles){
            dp[puddle[1]][puddle[0]] = -1;
        }

        for(int i=1; i<=n; ++i){
            for(int j=1; j<=m; ++j){
                if(dp[i][j] == 0){
                    //현재 좌표에서 위에 있는 곳이 방해물이면 -> 현재 좌표의 왼쪽 값을 그대로 넣어줌
                    if(dp[i-1][j] == -1) dp[i][j] = dp[i][j-1] + 0;

                    //현재 좌표에서 왼쪽에 있는 곳이 방해물이면 -> 현재 좌표의 위쪽 값을 그대로 넣어줌
                    else if(dp[i][j-1] == -1) dp[i][j] = dp[i-1][j] + 0;

                    //위, 왼쪽이 둘다 방해물이 아니라면 -> 현재 좌표의 위쪽 + 왼쪽 값을 넣어줌
                    else dp[i][j] = dp[i-1][j] + dp[i][j-1];

                    dp[i][j] %= 1000000007;
                }
            }
        }

        if(dp[n][m] == -1) return 0;
        answer = dp[n][m];

        return answer;
    }
}

 

<다시 풀어본 코드>

public class Problem_Tortoise {

    public static void main(String[] args) {
        int m = 4;  //열
        int n = 3;  //행
        int[][] puddles = {
                {2,2}
        };
        int answer = solution(m, n, puddles);
        System.out.println(answer);
    }

    public static int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] dp = new int[n+1][m+1];
        int nmg = 1000000007;

        //물 웅덩이 추가
        for(int[] puddle : puddles){
            dp[puddle[1]][puddle[0]] = -1;
        }

        dp[1][1] = 1;
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=m; ++j){
                if(dp[i][j] == -1) dp[i][j] = 0;
                else if(dp[i][j] == 0) {
                    //위쪽 + 왼쪽
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
                dp[i][j] %= nmg;
            }
        }

        answer = dp[n][m];
        return answer;
    }
}

 

 

[순위]

 

* 조건

1. n명의 권투 선수(1~n)와 각각의 경기 결과(results[][])가 주어진다
2. results[a][b]: a가 b를 이겼다라는 의미이다
3. 중간에 누락된 경기 결과가 있는 상황에서, 현재 주어진 결과를 통해 정확하게 랭킹을 알 수 있는 사람의 수를 출력한다

 

 

* 알고리즘

• 플로이드 워셜
  : 중간 지점을 추가하는 과정을 통해 최단 경로를 구한다
  : 모든 정점에 대한 최단 경로를 구할 수 있다

 

 

* 로직

• 주어진 경기 결과를 다시 생각해보면 이기든 지든 간에 직접적으로 연결되거나 다른 결과를 거쳐서 연결되는 경우의 수가 n-1이 된다면 정확한 랭킹을 유추할 수 있게 된다.
• 즉, 인접 행렬과 유사한 배열(matrix)을 만들고 각각 배열의 관계에서 중간 지점(1~n)을 거쳤을 때의 값과 기존 값을 비교한다. (matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]), / k: 중간 지점 노드)
• 이 과정을 반복하면 matrix가 갱신된다
• 갱신된 matrix를 가지고 대각선을 기준으로 대칭되는 두 곳 모두 값이 존재하지 않는다면(= 연결된 곳이 없다면) 해당 노드는 정확한 결과를 가질 수 없게 된다
• 값이 존재하는 부분이 n-1개인 곳을 카운팅하고 리턴한다

 

public class Problem_Ranking {

    public static void main(String[] args) {
        int n = 5;
        int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};

        int answer = solution(n, results);
        System.out.println(answer);
    }

    public static int solution(int n, int[][] results) {
        int answer = 0;
        int[][] matrix = new int[n+1][n+1];
        boolean[] impossibleNode = new boolean[n+1];
        final int MAX = 101;

        /*
            플로이드 와샬 (모든 정점에서 모든 정점으로의 최단거리)
                - 인접행렬 형태지만 해당 2차원 배열은 각 노드가 현재까지 연결된 가중치를 뜻함
                - 인접행렬을 순차적으로 돌 때, 노드와 노드 사이에 k라는 중간 노드(1~n)를 넣어보면서 갱신
                - v1~v2로 가는 비용 vs (v1~k + k~v2) 비용을 비교
        */

        //초기엔 max 값으로 선언 (가중치 갱신을 위해)
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=n; ++j){
                if(i == j) matrix[i][j] = 0;
                else matrix[i][j] = MAX;
            }
        }

        //입력값 넣기 (가중치가 따로 없기때문에 1로 갱신), 단방향
        for(int[] input : results){
            matrix[input[0]][input[1]] = 1;
        }

        //플로이드 와샬 적용
        for(int k=1; k<=n; ++k){
            for(int i=1; i<=n; ++i){
                for(int j=1; j<=n; ++j){
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                }
            }
        }

        //직접적이든 간접적이든 거치는 노드의 횟수가 n-1번이 된다면 결과를 구할 수 있다
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=n; ++j){
                if(i == j) continue;

                if(matrix[i][j] == MAX && matrix[j][i] == MAX) {
                    impossibleNode[i] = true;
                    break;
                }
            }
        }

        for(int i=1; i<=n; ++i){
            if(!impossibleNode[i]) answer++;
        }

       return answer;
    }
}

 

 

플로이드 워셜이라는 알고리즘은 처음 봤다. 위 문제처럼 직간접적으로 사용된 노드의 수를 찾는 방법으로는 유용할 것 같다는 생각이 들었다.