99클럽 코테 스터디 20일차 TIL - 그래프

오늘의 학습 키워드

그래프
플로이드-와샬 알고리즘

---

알고리즘 문제

• 프로그래머스 Level 3. 순위
• https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

---

공부한 내용

플로이드-와샬 알고리즘

• 그래프에서 모든 쌍의 최단 경로를 찾는 알고리즘.
• 이 문제에서 해당 알고리즘을 승패 관계에 대해 그래프로 만들어서, 그래프를 통해 간접적인 승패 관계를 도출할 수 있다.
• 플로이드-와샬 알고리즘
  • 출발지, 경유지, 도착지 노드들의 관계 속에서 출발지-경유지의 관계, 경유지-도착지의 관계를 통해 출발지-도착지의 관계를 간접적으로 알아내는 방식을 사용한다.

---

오늘의 회고

처음 시도

• 문제 풀이를 고민하면서, BFS에서 활용했던 인접 행렬에서 아이디어를 얻어 조금 다르지만 승패에 대한 값을 구분해 인접 행렬처럼 이차원 배열에 녹여야겠다고 생각했다.
• 그래서 이차원 배열 table 변수를 만들어서 column(열) 기준으로 row(행) 에 대해 이기면 1, 지면 -1로 초기화했다.
• 그렇게 만든 승패표(table)에서 1을 보고 A > B, B > C이면 A > C가 되도록 표에 1로 업데이트를 하도록 했다.
• 이렇게 승패표를 업데이트하는 메서드를 calculate()로 만들었는데, 경기결과를 전파할 때 문제가 있어서 테스트 케이스는 통과했지만, 제출 결과는 실패했다.

해결

• 내가 처음 만든 calculate() 메서드는 각 선수('x')가 이긴 대결 선수('y')로부터, 그 'y' 선수가 이긴 모든 선수('i')에 대한 관계를 table에서 1로 업데이트하려고 했다. => 모든 선수 간 가능한 경로를 파악하는 데 부족했다.
• 플로이드-와샬 알고리즘으로 해결해야 했다.
  • 3개의 중첩 반복문으로 모든 선수('x', 'y')에 대해 중간 선수('i')를 거쳐가는 경로가 승패 관계를 결정짓는데 도움이 되는지 확인해야 한다. => 'x' 선수 vs 'i' 선수의 승패 결과와 'i' 선수 vs 'y' 선수의 승패 결과
  • 선수 'i'가 선수 'j'를 간접적으로 이기는 모든 경로를 고려해서 테이블을 업데이트 해야 한다.
• 얻고자 하는 것
  
  • 'x' vs 'y' 선수의 대결 결과 도출 ( 3명 선수 x, i, y로 도출 가능)
    1. 'x' vs 'i' 결과와 'i' vs 'y' 결과로 x > i (x 승), i > y (i 승) 이면 x > y (x 승) 으로 간접적으로 결과를 알 수 있다.
    2. x' vs 'i' 결과와 'i' vs 'y' 결과로 x < i (x 패), i < y (i 패) 이면 x < y (x 패) 로 간접적으로 결과를 알 수 있다.

---

 

문제 풀이

처음 실패한 풀이

class Solution {
    //대회 참가한 총 권투선수의 수 : n명 (1 ~ n번 번호, 최대 100명)
    //경기 결과: 실력 순 (최대 4500번 경기)
    //return: 순위를 알 수 매길 수 있는 선수의 수
    int[][] results;
    int n;
    public void setTable(int[][] table) {
        for (int i = 0; i < results.length; i++) {
            table[results[i][0]][results[i][1]] = 1;
            table[results[i][1]][results[i][0]] = -1;
        }
    } 
    
    public void calculate(int[][] table) {
        for (int x = 1; x < n+1; x++) {
            for (int y = 1; y < n+1; y++) {
                if (table[x][y] == 1) {
                    for (int i = 1; i < n+1; i++) {
                        if (table[y][i] == 1) {
                            table[x][i] = 1;
                            table[i][x] = -1;
                        }
                    }
                }
            }
        }
    }
    
    public int counting(int[][] table) {
        int count = 0;
        for (int i = 1; i < table.length; i++) {
            int zero = 0;
            for (int j = 1; j < table[0].length; j++) {
                if (table[i][j] == 0) zero++;
            }
            if (zero < 2) count++;
        }
        
        return count;
    }
    
    public int solution(int n, int[][] results) {
        int count = 0;
        this.results = results;
        this.n = n;
        int[][] table = new int[n+1][n+1];
        
        setTable(table);
       
        calculate(table);
       
        count = counting(table);
        
        return count;
    }
}

 

플로이드-와샬 알고리즘으로 결과 전파를 수정한 풀이

class Solution {
    int[][] results;
    int n;
    //승패표 초기화
    public void setTable(int[][] table) {
        for (int i = 0; i < results.length; i++) {
            table[results[i][0]][results[i][1]] = 1;
            table[results[i][1]][results[i][0]] = -1;
        }
    } 
    
    //플로이드-와샬 알고리즘
    public void calculate(int[][] table) {
        for (int i = 1; i < n+1; i++) {	//경유지 (관계 이용할 선수)
            for (int x = 1; x < n+1; x++) { //출발지 (간접 관계로 승패 가릴 선수)
                for (int y = 1; y < n+1; y++) {	//도착지 (간접 관계 승패 가릴 선수)
                	if (table[x][i] == 1 && table[i][y] == 1) //이긴 결과로 간접 결과 도출
                        table[x][y] = 1;
                    else if (table[x][i] == -1 && table[i][y] == -1) //패배 결과로 간접 결과 도출
                        table[x][y] = -1;
                }
            }
        }
    }
    
    //순위 알 수 있음: row (한 선수)에 대해 승패 결과가 자기 자신과의 대결(0)을 뺀 나머지가 있어야 한다.
    //순위 알 수 없음: row에 0(결과 없음)이 2개 이상인 경우
    public int counting(int[][] table) {
        int count = 0;
        for (int i = 1; i < table.length; i++) {
            int zero = 0;
            for (int j = 1; j < table[0].length; j++) {
                if (table[i][j] == 0) zero++;
            }
            if (zero < 2) count++;
        }
        
        return count;
    }
    
    public int solution(int n, int[][] results) {
        int count = 0;
        this.results = results;
        this.n = n;
        int[][] table = new int[n+1][n+1];	//승패표
        
        setTable(table);
       
        calculate(table);
       
        count = counting(table);
        
        return count;
    }
}