[프로그래머스] 도넛과 막대 그래프 - 자바(Java)
문제 링크
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
도넛 모양 그래프, 막대 모양 그래프, 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 함수를 완성해 주세요.
제한사항
- 1 ≤ edges의 길이 ≤ 1,000,000
- edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
- 1 ≤ a, b ≤ 1,000,000
- 문제의 조건에 맞는 그래프가 주어집니다.
- 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.
입출력 예
| edges | result |
| [[2, 3], [4, 3], [1, 1], [2, 1]] | [2, 1, 1, 0] |
| [[4, 11], [1, 12], [8, 3], [12, 7], [4, 2], [7, 11], [4, 8], [9, 6], [10, 11], [6, 10], [3, 5], [11, 1], [5, 3], [11, 9], [3, 8]] | [4, 0, 1, 2] |
문제 풀이
[고려사항]
edges는 최대 1,000,000(백만)이기 때문에 시간 복잡도 n^2을 조심해야한다.
[알고리즘, 구현방법]
먼저 기준이 되는 중앙노드를 판별해야한다.
그래프들과 무관한 정점을 중앙 노드라하면, 중앙 노드는 out 간선이 무조건 2개 이상인 노드이다.
제한사항에 나와있듯 나올 수 있는 그래프 개수는 2개 이상이므로, 중앙 노드에서 연결해야하는 노드는 2개 이상이기 때문에 중앙 노드에서 뻗어나가는 간선만 있고, 그 간선의 개수는 2개 이상이어야 한다.
도넛, 막대, 8자 모양 그래프에서 나가는 간선만 있으면서 그 간선 수가 2개 이상인 것은 없다.
그래서 중앙 노드 판별을 위와 같이 할 수 있다.
X 1차 생각
- edges를 순회하면서 각 노드별 들어오는 간선, 나가는 간선, 자식 노드, 해당 노드에 연결된 노드를 Node 객체에 저장하고 중앙 노드의 자식 노드를 중심으로 순회한다.
- 중앙 노드에 연결된 자식 노드를 순회할때는 각 자식 노드에서도 자식 노드를 순회하면서 해당 노드의 간선을 계산한다.
- 중앙 노드에 연결된 자식 노드의 순회가 끝날때까지 2번을 반복한다.
- 중앙 노드에 연결된 자식 노드의 자식 노드 순회도 끝나면, 저장한 간선 수와 노드 수로 그래프 모양을 판별한다.
이렇게 하면 테스트 케이스 22, 26번에서 런타임 에러가 발생한다.
edges가 크게 주어질때 재귀 깊이가 초과해서 발생하는 것으로 보인다.
* 재귀 호출을 하면 호출된 메서드에서 사용할 변수가 메모리에 추가 할당되기에 너무 깊이 들어가면 메모리가 차서 StackOverFlowError 예외가 발생한다.
✅ 2차 생각
런타임 에러 관련해서 찾아보다가, 들어오고 나가는 간선을 기준으로 그래프 모양을 판별하라는 힌트를 보고, 코드를 수정했다.
도넛 모양, 막대 모양, 8자 모양 그래프의 각각 고유한 특성을 확인했다.
*이렇게 하니까 속도와 메모리 차이가 2배 이상 차이났다..!
- 막대 모양 : 단방향이기 때문에 Root 노드는 들어오는 간선 수가 0개이면서 나가는 간선은 1개이고, Leaf 노드는 들어오는 간선 수가 1개이면서 나가는 간선은 0개인 경우
- 도넛 모양 : 모든 노드가 들어오는 간선 수가 1개이면서 나가는 간선도 1개인 경우
- 8자 모양 : 정점으로 들어오는 간선 수가 2개이면서 나가는 간선도 2개인 경우 (=8자 모양의 중앙 노드)
이때 모든 그래프에 있는 경우는, 들어오는 간선이 1개이면서 나가는 간선도 1개인 경우이다.
이때는 해당 노드의 방문 여부와 자식 노드를 확인해서 재탐색하면 그래프 모양 확인이 가능하다.
즉, 들어오고 나가는 간선 수가 모두 1개인 경우, 해당 노드의 자식노드를 탐색하거나 이미 방문한 노드인지 확인하여 판별한다.
- 도넛 모양의 경우, 들어오고 나가는 간선 수가 1개인데 이미 방문한 노드라면 판별이 가능하다.
- 막대 모양의 경우, 중간에 있는 노드면 위의 경우가 되는데, 이때 막대 모양 그래프는 Leaf 노드까지 방문해서 Leaf 노드에 도달하면 들어오는 간선 수가 1개이면서 나가는 간선 수가 0개이므로 판별이 가능하다.
- 8자 모양의 경우, 중간에 있는 노드가 무조건 들어오는 간선 수가 2개, 나가는 간선 수가 2개이고, 8자 모양 그래프를 모두 탐색하려면 무조건 8자 모양 그래프의 중앙 노드를 거치게 되므로 판별이 가능하다.
* 8자 모양의 경우, 도넛 모양이 2개 합쳐진 모양이지만, 시작 노드에서 전체 탐색을 하고 다시 돌아와야 이미 방문한 노드를 재방문하므로 도넛 모양과 별개로 판별 가능
[풀이 과정]
- edges를 순회하면서 노드 정보 저장
- Node 객체 : 들어오는 간선 수(in), 나가는 간선 수(out), 자식노드 리스트(childNodeList)
- 예시) [2,3]
- 2번 노드에는 나가는 간선 수 +1 & 자식노드 리스트에 3추가
- 3번 노드에는 들어오는 간선 수 +1
- 저장한 노드 정보로 중앙노드 찾기
- 들어오는 간선(in) == 0 && 나가는 간선(out) >= 2
- 중앙 노드의 자식 노드를 순회
- 그래프 하나씩 확인해야하므로, 깊이 탐색을 위해 Stack에 자식노드 번호 저장
- Stack 이 비워질 때까지 아래 과정 반복
- 해당 노드에서 그래프 모양 판별이 가능하다면 판별하여 각 그래프 수 +1
- 8자 모양이나 막대 모양 그래프의 고유한 특징으로 판별이 가능하다면 각 그래프 수 +1
- 아니라면, 노드 방문여부 확인
- 방문한 노드이면서 들어오고 나가는 간선 수가 1개라면 (in == 1 && out == 1) 도넛 모양 그래프 수 +1
- 아니라면, 해당 노드의 자식 노드를 Stack에 push해서 해당 노드 위와 같은 과정으로 탐색
- 해당 노드에서 그래프 모양 판별이 가능하다면 판별하여 각 그래프 수 +1
- 중앙 노드 번호, 각 그래프 수 반환
정답 코드
import java.util.*;
public class Solution {
public class Node {
int in = 0; // 들어오는 간선
int out = 0; // 나가는 간선
boolean visited = false;
List<Integer> childNodeList = new ArrayList<>(); // 자식 노드 (=나가는 간선이 가리키는 노드)
public Node(int child) {
if (child != 0) this.addChildNode(child); // 자식 노드가 있을때
else this.in++;
}
public void addChildNode(int child) {
this.out++;
this.childNodeList.add(child);
}
}
public int[] solution(int[][] edges) {
/**
* 방문한 노드인데 자식 노드로 재방문하는 경우, 도넛 모양
* 단방향이라 무조건 한번씩만 방문하는 막대 모양 그래프는, Leaf 노드가 in=1, out=0 | Root 노드는 in=0, out=1
* in=2, out=2인 노드가 있으면 8자 모양
*/
int donut = 0;
int bar = 0;
int eight = 0;
Map<Integer, Node> nodeMap = new HashMap<>(); // key: Node num, value: Node 정보
// Node Setting
for (int[] edge: edges) {
int node = edge[0];
int childNode = edge[1];
if (nodeMap.containsKey(node)) nodeMap.get(node).addChildNode(childNode);
else nodeMap.put(node, new Node(childNode));
if (nodeMap.containsKey(childNode)) nodeMap.get(childNode).in++;
else nodeMap.put(childNode, new Node(0));
}
// 중앙 노드 찾기
int middle = 0;
Iterator<Integer> it = nodeMap.keySet().iterator();
while (it.hasNext()) {
int nodeNum = it.next();
Node node = nodeMap.get(nodeNum);
// 들어오는 간선(in), 나가는 간선(out) 계산
if (node.in == 0 && node.out >= 2) {
middle = nodeNum;
break;
}
}
Stack<Integer> searchStack = new Stack<>(); // 탐색할 노드 번호 (깊이 탐색을 해야하기 때문에 Stack)
for (int child: nodeMap.get(middle).childNodeList) {
searchStack.push(child);
nodeMap.get(child).in--; // 중앙 노드에서 들어오는 선 제외
}
// Find Graph
while (!searchStack.isEmpty()) {
Node child = nodeMap.get(searchStack.pop());
int in = child.in;
int out = child.out;
if (in == 2 && out == 2) {
eight++;
} else if ((in == 0 && out == 0) || (in == 1 && out == 0) || (in == 0 && out == 1)) {
bar++;
} else {
if (child.visited && (in == 1 && out == 1)) donut++;
else if (!child.childNodeList.isEmpty()) for (int num: child.childNodeList) searchStack.push(num);
}
child.visited = true;
}
return new int[]{middle, donut, bar, eight};
}
}