프로그래머스/자바 Lv2
[프로그래머스] Java Lv2. 코딩테스트 연습 > 2024 KAKAO WINTER INTERNSHIP > 도넛과 막대 그래프
행수쌤
2024. 11. 30. 17:49
728x90
반응형
문제설명
- 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있다.
- 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가다 보면 n-1개의 정점들을 한 번 씩 방문 뒤 원래 정점으로 돌아온다.
- 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있다.
- 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재한다.
- 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있다.
- 크기가 동일한 2개의 도넛 모양 그래프에서 정을 하나씩 골라 결합한 형태이다.
- 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러개 있다.
- 이 그래프들과 무관한 정점을 하나 생성 한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했다.
- 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프 수, 막대 모양 그래프 수, 8자 모양 그래프 수를 구해야 한다.
제한사항
- 1 <= edges의 길이 <= 1,000,000
- 그래프의 수의 합은 2 이상
접근방법
- 뭐니뭐니해도 가장 어려운 일이지만 코드를 짜기 전에 문제를 잘 이해해야 한다. 생성 정점을 잘못 이해하고 코드 먼저 짰다가 코드 완전히 다시 짬..
- '이 그래프들과 무관한 정점을 하나 생성 한 뒤' -> 생성 정점은 도넛, 막대, 8자 그래프가에 포함되는게 아니라 단 하나 독립적으로 존재하여 각각의 그래프로 뻗어나가는 간선만 존재한다.
- 각 그래프간에 간선으로 연결되어 있지 않으므로, 생성 정점에서 간선을 통해 한 정점에 도달하면, 그 정점이 어떤 그래프에 포함된 놈인지만 판단하면 된다.
- 생성 정점을 먼저 파악하는게 좋아보인다. 생성 정점을 어떻게 알 수 있을까? 우선 모든 간선이 밖으로 나가는 놈이다. 모든 간선이 밖으로 나가는 놈이 생성 정점밖에 없을까? 막대 그래프의 가장 아래 정점일 가능성이 있으나 그래프의 합은 2 이상이므로 생성 정점에서 나가는 노드는 최소 2개이다.
- 생성 정점에서 온 간선을 제외하고 각 그래프에서 간선을 따라 정점들을 방문하면서 그래프의 특성을 파악한다.
- 직선 그래프는 정점에서 나가는 간선이 없는 정점이 발견된다.
- 8자 그래프는 정점에서 나가는 간선이 2개인 정점이 발견된다.
- 도넛 그래프는 방문했던 정점을 다시 방문하게 된다.
핵심로직
- 정점의 개수를 파악한다.
- 그래프 초기화 => 정점(index) 에서 밖으로 나가는 간선을 담는 리스트와 정점으로 들어오는 간선의 수를 카운트 하는 리스트를 생성한다.
- 생성 정점 탐색 => 정점을 돌면서 나가는 간선이 2개 이상이고 들어오는 간선은 없는 정점을 찾는다.
- 그래프 분리 => 생성 정점의 간선을 따라 도착한 정점들의 들어오는 간선 수 카운트를 -1 해준다.
- 그래프 파악 => 분리된 각각의 그래프를 돌면서 그래프의 특징에 따라 그래프 카운트를 해준다.
- 직선 그래프는 정점에서 나가는 간선이 없는 정점이 발견된다.
- 8자 그래프는 정점에서 나가는 간선이 2개인 정점이 발견된다.
- 도넛 그래프는 방문했던 정점을 다시 방문하게 된다.(Queue 사용)
입출력 예
- edges = [[2, 3], [4, 3], [1, 1], [2, 1]]
- result = [2, 1, 1, 0]
코드 작성
import java.util.*;
class Solution {
// 전체 정점의 개수 카운트
private static int nodeCount = 0;
// 정점(index) 에서의 간선 방향을 담은 리스트
private static List<List<Integer>> graph = new ArrayList<>();
// 각 정점으로 들어오는 간선의 개수
private static List<Integer> entranceCount = new ArrayList<>();
private static boolean[] visited;
public int[] solution(int[][] edges) {
int donut = 0;
int stick = 0;
int eight = 0;
// 1. 정점 개수 파악
for(int i=0; i<edges.length; i++) {
nodeCount = Math.max(nodeCount, Math.max(edges[i][0], edges[i][1]));
}
visited = new boolean[nodeCount+1];
// 2. 그래프 초기화
for(int i=0; i<=nodeCount; i++) {
graph.add(new ArrayList<>());
entranceCount.add(0);
}
for(int i=0; i<edges.length; i++) {
graph.get(edges[i][0]).add(edges[i][1]);
entranceCount.set(edges[i][1], entranceCount.get(edges[i][1]) +1);
}
// 3. 생성 정점 탐색
int startNum = findStartNum();
List<Integer> startWay = graph.get(startNum);
// 4. 그래프 분리
for(int i=0; i<startWay.size(); i++) {
entranceCount.set(startWay.get(i), entranceCount.get(startWay.get(i)) -1);
}
// 5. 그래프 파악
for(int i=0; i<startWay.size(); i++) {
int node = startWay.get(i);
Queue<Integer> numQ = new LinkedList<>();
while(true) {
if(graph.get(node).size() == 2 && entranceCount.get(node) == 2) {
eight ++;
break;
} else if(graph.get(node).size() == 0) {
stick ++;
break;
} else {
for(int j=0; j<graph.get(node).size(); j++) {
if(!visited[graph.get(node).get(j)]) {
numQ.add(graph.get(node).get(j));
visited[graph.get(node).get(j)] = true;
}
}
if(numQ.size() > 0) {
node = numQ.poll();
} else {
donut ++;
break;
}
}
}
}
return new int[]{startNum, donut, stick, eight};
}
// 3. 생성 정점 탐색
private static int findStartNum() {
int index = -1;
for(int i=1; i<=nodeCount; i++) {
if(graph.get(i).size() >= 2 && entranceCount.get(i) == 0) {
index = i;
break;
}
}
return index;
}
}정답을 맞추긴 했지만 가독성이 다소 떨어지고 도넛 그래프 파악을 위한 Queue의 사용이 조금 애매하다. Queue를 사용해 도넛그래프를 파악하는 개념은 유지하되, queue가 빈 상태에서 그래프 파악이 안 됐다면 도넛 그래프임이 확실하므로, while(true)를 while(!queue.isEmpty())로 바꿔준다.
코드 작성(2차)
import java.util.*;
class Solution {
private static int nodeCount = 0; // 전체 정점의 개수
private static List<List<Integer>> graph = new ArrayList<>(); // 각 정점의 간선 정보
private static List<Integer> entranceCount = new ArrayList<>(); // 각 정점으로 들어오는 간선의 개수
private static boolean[] visited; // 방문 여부
public int[] solution(int[][] edges) {
int donut = 0, stick = 0, eight = 0;
// 1. 정점 개수 파악
for (int[] edge : edges) {
nodeCount = Math.max(nodeCount, Math.max(edge[0], edge[1]));
}
visited = new boolean[nodeCount + 1];
// 2. 그래프 초기화
for (int i = 0; i <= nodeCount; i++) {
graph.add(new ArrayList<>());
entranceCount.add(0);
}
// 3. 간선 정보 입력
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
entranceCount.set(edge[1], entranceCount.get(edge[1]) + 1);
}
// 4. 생성 정점 탐색
int startNum = findStartNum();
List<Integer> startWay = graph.get(startNum);
// 5. 생성 정점과 연결된 정점의 간선 제거
for (int node : startWay) {
entranceCount.set(node, entranceCount.get(node) - 1);
}
// 6. 그래프 파악
for (int node : startWay) {
if (!visited[node]) {
int type = exploreGraph(node);
if (type == 0) donut++;
else if (type == 1) stick++;
else if (type == 2) eight++;
}
}
return new int[]{startNum, donut, stick, eight};
}
// 생성 정점 탐색
private static int findStartNum() {
for (int i = 1; i <= nodeCount; i++) {
if (graph.get(i).size() >= 2 && entranceCount.get(i) == 0) {
return i;
}
}
return -1;
}
// 그래프 탐색 및 유형 판별
private static int exploreGraph(int startNode) {
Queue<Integer> queue = new LinkedList<>();
queue.add(startNode);
visited[startNode] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
if (graph.get(node).size() == 2 && entranceCount.get(node) == 2) {
return 2; // 8 형태
} else if (graph.get(node).isEmpty()) {
return 1; // 막대 형태
} else {
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
}
}
}
}
return 0; // 도넛 형태
}
}
728x90
반응형