[2024 KAKAO INTERN] 도넛과 막대 그래프

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

프로그래머스

 

문제 유형

• 그래프

 

문제 난이도

• Lev2

 

문제 분석

간선들의 정보가 주어진다. 간선들은 단방향 그래프이고, 정점과 간선을 통해서 해당 그래프가 어떤 모양의 그래프인지를 카운팅하고, 새로 생성된 정점의 위치를 찾는 문제이다.

처음에 문제를 접근할 때에는 DFS를 통해 그래프 탐색을 하려고 했지만, 이후 백트래킹을 하는 과정에서 중복 연산이 되고, 작성해야하는 엣지 케이스와 예외들을 처리하는게 많아져 다른 방법을 탐색했다.

그래프의 특성을 보면 문제는 쉽게 풀린다.

0. 새로 생성된 정점의 경우, 나가는 간선만 있고, 들어오는 간선만 있다. 그리고 문제에서 그래프의 개수는 2개 이상이고, 해당 정점은 모든 그래프와 연결된다고 하였으니,

if(나가는 간선의 개수 - 들어오는 간선의 개수 > 1) then "새로 생성된 정점"
새로 생성된 정점의 나가는 간선의 개수 = 총 그래프의 개수

1. 도넛 모양의 그래프의 경우, 들어오는 간선과 나가는 간선의 개수가 같으면서 1개씩으로 동일하지만, 같은 그래프에서 나온 정점인지를 확인하기 위해서는 방문 처리를 해야하는데 그럼 복잡해진다.

2. 막대 모양의 그래프의 경우, 마지막 정점이 나가는 간선은 없고, 들어오는 간선은 0보다 큰 경우에 대한 정점의 개수만 세주면 그래프의 개수가 나온다. (여기서 SIZE = 1 인 경우는 들어오는 간선의 개수가 없지 않냐라고 생각할 수 있는데, 필자도 그렇게 생각하고, 들어오는 간선에 대한 조건을 빼고 진행하다보니 테스트케이스 35번에서 계속 실패가 떴다.)
그러나, 새로 생성된 정점이 모든 그래프에 나가는 간선을 연결하다보니, 정점이 한 개인 경우도 들어오는 간선의 개수가 하나 생기게 된다.

정점 i에 대하여, if(out[i] == 0 && in[i] > 0) then "막대 모양의 그래프"++;

3. 8자 모형의 그래프의 경우, 한 정점이 들어오는 간선 2개, 나가는 간선 2개가 고정으로 한 개씩 존재하므로 해당 정점의 개수를 통해서 8자 모형 그래프의 개수를 셀 수 있다. (새로 생성된 정점의 들어오는 개수가 추가 되기 때문에, "이상"으로 표현하였다.)

정점 i에 대하여, if(out[i] >= 2 && in[i] >=2) then "8자 모양의 그래프"++;

결론:
result[2]: 막대 모양의 그래프의 개수
result[3]: 8자 모형의 그래프의 개수

도넛 모양의 그래프(result[1]) = 새로 생성된 정점의 나가는 개수(result[0]) - result[2] - result[3] 

 

 

전체 코드

import java.util.*;
import java.io.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] result = new int[4];
        int idx = 0;
        
        for(int i = 0; i < edges.length; i++) {
            idx = Math.max(idx, Math.max(edges[i][0], edges[i][1]));
        }
        
        int[] in = new int[idx + 1];
        int[] out = new int[idx + 1];
        
        for(int i = 0; i < edges.length; i++) {
            out[edges[i][0]]++;
            in[edges[i][1]]++;
        }
        
        for(int i = 1; i < idx + 1; i++) {
            if(out[i] - in[i] > 1) {
                result[0] = i;
                break;
            }
        }
        
        for(int i = 1; i < idx + 1; i++) {            
            if(out[i] >= 2 && in[i] >= 2) result[3]++;
            if(out[i] == 0 && in[i] > 0) result[2]++;
        }
        
        result[1] = out[result[0]] - result[2] - result[3];
        
        return result;
    
    }
}