99클럽 코테 스터디 25일차 TIL + 그래프 + BFS(순위)

오늘의 과제

프로그래머스 Lv.3으로 분류된 순위입니다.

 

이번 유형은 BFS(넓이 우선 탐색, 그래프) 입니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

선수의 수 n과 경기 결과를 담은 2차원 배열이 주어질 때 정확하게 순위를 알 수 있는 선수의 수를 반환하는 문제입니다.

 

문제의 유형처럼 그래프 + BFS이니 기본 공식처럼 셋팅을 시작합니다.

 

첫 번째 셋팅으로 ArrayList를 통해 서로간의 간선을 표현할 것이기 때문에 초기화를 진행합니다.

List<Integer>[] wins = new ArrayList[n + 1];
List<Integer>[] losses = new ArrayList[n + 1];

for (int i = 0; i <= n; i++) {
    wins[i] = new ArrayList<>();
    losses[i] = new ArrayList<>();
}

 

wins와 losses 두 개의 그래프로 진행하는 이유는 정확하게 순위를 매기려면 해당 선수가 모든 선수들과의 관계가 있어야 하기 때문입니다. 선수라는 표현이 어렵다면 "해당 노드가 다른 노드들과도 모두 연결되어 있는가?" 로 생각하면 이해하기 편합니다.

 

이제 각 선수마다 승,패 기록을 카운트하기 위해 results 배열을 통해 간선을 표시합니다.

for (int[] result : results) {
    int winner = result[0];
    int loser = result[1];
    wins[winner].add(loser); // winner가 이긴 선수들
    losses[loser].add(winner); // loser가 진 선수들
}

 

BFS 로직은 정말 공식같이 방문여부 확인, 이어져있는 간선이 있다면 큐에 추가만 하는 간단한 로직을 수행합니다.

이겼을 때, 졌을 때 총 두 번의 BFS를 반복하면 해당 선수가 무슨 노드와 연결되어 있는지 확인할 수 있습니다.

private int bfs(List<Integer>[] graph, int start) {
    boolean[] visited = new boolean[graph.length];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    int count = 0;

    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
                count++;
            }
        }
    }

    return count;
}

 

 

이겼을 때의 간선, 졌을 때의 간선을 모두 더하면 이 선수가 몇명의 선수와 경기를 진행했는지 알 수 있고 경기를 치른 선수의 수가 n - 1(본인제외)이면 모든 선수와의 경기 기록이 있다는 뜻이니 해당 선수는 경기 결과를 명확히 알 수 있습니다.

for (int i = 1; i <= n; i++) {
    int winCount = bfs(wins, i); // i 선수가 이긴 선수의 수
    int lossCount = bfs(losses, i); // i 선수가 진 선수의 수
    if (winCount + lossCount == n - 1) {
        answer++;
    }
}

 

 

전체 코드입니다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        List<Integer>[] wins = new ArrayList[n + 1];
        List<Integer>[] losses = new ArrayList[n + 1];
        
        for (int i = 0; i <= n; i++) {
            wins[i] = new ArrayList<>();
            losses[i] = new ArrayList<>();
        }
        
        for (int[] result : results) {
            int winner = result[0];
            int loser = result[1];
            wins[winner].add(loser); // winner가 이긴 선수들
            losses[loser].add(winner); // loser가 진 선수들
        }
        
        for (int i = 1; i <= n; i++) {
            int winCount = bfs(wins, i); // i 선수가 이긴 선수의 수
            int lossCount = bfs(losses, i); // i 선수가 진 선수의 수
            if (winCount + lossCount == n - 1) {
                answer++;
            }
        }
        
        return answer;
    }
    
    private int bfs(List<Integer>[] graph, int start) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor : graph[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                    count++;
                }
            }
        }

        return count;
    }
}

 

배운 점

 

BFS가 수행하는 로직은 이전에 너무 많이 썻고 참조할 레퍼런스가 많기 때문에 쉽게 작성했는데 본문에 서술한 "해당 노드가 다른 노드들과도 모두 연결되어 있는가?" 라는 발상은 바로 하지 못했습니다. 사실 이미 답을 아는 시점에서는 승리 횟수 + 패배 횟수 == n - 1이면 모든 노드를 방문했다라는게 당연하지만 아직은 바로 떠올리질 못하네요.

 

하지만 이전 이분탐색과 마찬가지로 그래프 문제를 조금 반복해서 풀어본다면 기본 틀은 비슷하고 핵심 문제 요건만 도출해내면 풀 수 있는 문제들이니 조금은 설레기도 합니다. 공부의 목적이 이직시 코딩 테스트의 통과라지만 이 기회에 알고리즘에 재미를 붙여 수수께끼나 퍼즐을 하는 느낌으로 간간히 풀 수 있는 취미가 되길 바래봅니다.

 

 

오늘의 한줄평

코딩 테스트 실무에 쓸모 없다는 고인물 특 = Lv.1도 못품, 자료구조는 List랑 Map밖에 모름.