출처
https://school.programmers.co.kr/learn/courses/30/lessons/258711
문제
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.
-
크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.
-
크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습니다.
-
크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 8자 모양 그래프의 형태는 다음과 같습니다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.
그 후 각 정점에 서로 다른 번호를 매겼습니다.
이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.
그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
접근 방법
처음엔 그래프 이론으로 순환 구조인지 등을 판별해서 복잡하게 다 구현해야하나? 라고 어렵게 생각했던것 같습니다. 하지만 문제를 잘 보면 각 그래프 별로 특징이 있어서, 그것을 잘 캐치하면 되는 문제였습니다.
먼저, 모든 그래프와 연결되어있는 시작 정점을 찾습니다. 이 시작 정점은 들어오는 간선은 존재하지 않지만, 나가는 정점은 2개 이상 존재합니다(문제 조건).
먼저 Map에 모든 노드의 간선의 정보를 저장한 후, 들어오는 간선의 갯수가 없으면서 나가는 정점이 2개 이상 존재하는 시작 정점을 찾아, 그 정점이 연결되어 있는 노드를 모두 저장합니다. 이 노드들은 각 그래프의 임의의 한 노드라고 되어있음으로, 이 노드들을 기준으로 모든 그래프를 탐색하여 갯수를 탐색하면 됩니다.
그리고 아래 조건을 통해 그래프의 모양을 판별해 줍니다.
- 막대 그래프는, 들어오는 간선이 1개이고 나가는 간선이 없는 노드가 존재한다.
- 8자 그래프는, 들어오는 간선이 2개고 나가는 간선이 2개인 노드가 존재한다.
- 이 외 도넛 그래프는 방문했던 노드를 다시 방문하게 되고, 이 방문했던 노드와 연결된 노드 중 새로운 노드가 없을때 판별한다.
- 사실 도넛그래프는 막대인지 8자인지만 판별해서, 아닐 경우 도넛 그래프라고 간단하게 판별이 가능하다.
이 조건을 세웠으면, 아까 모아둔 시작점 노드들에 대해 BFS 탐색을 진행하여 그래프의 종류를 판별하여 결과값을 저장한다.
코드
import java.util.*;
public class pgs258711 {
boolean[] visited;
int[] answer;
Map<Integer, List<Integer>> map;
Map<Integer, Integer> inbound_cnt;
public int[] solution(int[][] edges) {
answer = new int[4];
int node_cnt = 0;
map = new HashMap<>();
inbound_cnt = new HashMap<>();
for (int[] edge : edges) {
node_cnt = Math.max(node_cnt, Math.max(edge[0], edge[1]));
map.computeIfAbsent(edge[0], x -> new ArrayList<>()).add(edge[1]);
inbound_cnt.put(edge[1], inbound_cnt.getOrDefault(edge[1], 0) + 1);
}
visited = new boolean[node_cnt + 1];
// 각 그래프별 임의의 정점 집합
List<Integer> startPoint = new ArrayList<>();
// 새로 생성된 정점을 찾고, 제거
for (int x : map.keySet()) {
if (inbound_cnt.get(x) == null && map.get(x).size() >= 2) {
startPoint.addAll(map.get(x));
map.remove(x);
answer[0] = x;
break;
}
}
for (int node : startPoint) {
// 들어오는 간선의 갯수에서, 시작 정점에서 들어오는 간선의 수를 빼준다.
inbound_cnt.put(node, inbound_cnt.get(node) - 1);
if (!visited[node]) {
answer[checkGraph(node)]++;
}
}
return answer;
}
// 도넛 1, 막대 2, 8자 3
public int checkGraph(int node) {
Deque<Integer> dq = new ArrayDeque<>();
visited[node] = true;
dq.add(node);
while (!dq.isEmpty()) {
int now = dq.poll();
if (map.get(now) == null) { // 막대인 경우
return 2;
} else if (inbound_cnt.get(now) == 2 && map.get(now).size() == 2) { // 8인 경우
return 3;
} else {
for (int x : map.get(now)) {
if (!visited[x]) {
dq.add(x);
visited[x] = true;
}
}
}
}
return 1;
}
}
