티스토리 뷰
[JAVA] 알고리즘 스터디 6주 차 공통과제: KAKAO 도넛과 막대그래프
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
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 자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다. 그 후 각 정점에 서로 다른 번호를 매겼습니다.
이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8 자 모양 그래프의 수를 구해야 합니다. 그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
🔎 풀이
처음에 풀 때는 DFS로 edges 배열의 방문 여부를 저장하는 visited 배열을 사용해서 연결된 노드를 탐색해 그래프를 모두 확인하는 방식으로 코드를 구성했다. 그런데 예외도 너무 많고, 로직도 복잡해서 많이 헤맸다. 그래도 열심히 풀었는데 그렇게 푼 결과는 실패였다..
🔹 그래프를 모두 탐색하는 풀이(실패)
import java.util.*;
class Solution {
public int[] solution(int[][] edges) {
Map<Integer,Integer> directedNodes = new HashMap<>(); // 노드 번호와 해당 노드를 향하는 간선 수 저장
Map<Integer,Integer> startingNodes = new HashMap<>(); // 노드 번호와 해당 노드에서 시작하는 간선 수 저장
boolean[] visited = new boolean[edges.length];
int doughnut_cnt = 0;
int stick_cnt = 0;
int figure8_cnt = 0;
for( int i = 0; i < edges.length; i++ ){
int from = edges[i][0];
int to = edges[i][1];
// 노드 맵에 삽입
if( startingNodes.containsKey(from)){
startingNodes.replace(from,startingNodes.get(from)+1);
}
else startingNodes.put(from,1);
if( !startingNodes.containsKey(to)){
startingNodes.put(to,0);
}
if( directedNodes.containsKey(to)){
directedNodes.replace(to,directedNodes.get(to)+1);
}
else directedNodes.put(to,1);
if( !directedNodes.containsKey(from)){
directedNodes.put(from,0);
}
}
System.out.println(startingNodes.toString());
System.out.println(directedNodes.toString());
int extraNode = 0;
Queue<Integer> centerOfFigure8 = new LinkedList<>();
// 추가한 노드 찾기 & 8자 그래프의 중심 탐색
for( int i = 1; i < directedNodes.size()+1; i++ ){
if( directedNodes.get(i)==0 && startingNodes.get(i) != 1 ){
extraNode = i; // 추가한 노드 발견
}
else if( startingNodes.get(i) != 1 ){
centerOfFigure8.offer(i);
}
}
System.out.println(extraNode);
// 8자 그래프부터 탐색
while(!centerOfFigure8.isEmpty()){
int center = centerOfFigure8.poll();
figure8_cnt++;
for( int i = 0; i < edges.length; i++){
if( edges[i][0] == center ){
visited[i] = true;
int to = edges[i][1]; // 1
// 그래프 탐색
for( int j = 0; j < edges.length; j++ ){
if( edges[j][0] == to ){
visited[j] = true;
to = edges[j][1];
if( to == center ) break;
}
}
}
}
}
System.out.println(Arrays.toString(visited));
// 나머지 막대 그래프와 도넛 그래프 탐색
for( int i = 0; i < edges.length; i++ ){
if( edges[i][0] == extraNode || visited[i] ) continue;
// 그래프 탐색 시작 노드 체크
visited[i] = true;
int to = edges[i][1];
Set<Integer> graph = new HashSet<>();
graph.add(edges[i][0]);
graph.add(to);
// 본인을 가리키는 막대그래프
if(edges[i][0] == to) {
doughnut_cnt++;
continue;
}
for( int j = 0 ; j < edges.length; j++ ){
if( edges[j][0] == to && !visited[j] ){ // 다음 노드 발견
visited[j] = true;
to = edges[j][1];
// 순환성 있는지 확인
if(graph.contains(to)){ // 순환 발견
doughnut_cnt++;
break;
}
else graph.add(to);
}
else if( j == edges.length -1 ){ // 막대 그래프
stick_cnt++;
}
}
}
return new int[]{ extraNode, doughnut_cnt, stick_cnt, figure8_cnt };
}
}
결국 검색 찬스로 다른 뾰족한 방법이 있을까 하고 찾아봤는데 역시 세상에는 천재가 참 많다는 것을 다시 한번 느꼈다.
생각을 전환해 보면, 노드를 모두 탐색하며 그래프를 다 그려나갈 필요 없이 각 그래프의 특징만 안다면 그 그래프를 '대표하는 노드'만 골라내서 개수를 세면 그것이 바로 각 그래프의 개수가 되는 것이다.
예를 들면 다음과 같다.
먼저 막대그래프의 대표 노드라고 할 수 있는 것은 막대 노드의 가장 마지막 리프 노드이다. 들어가는 간선은 있고, 나오는 간선은 없다.
그리고 8자 그래프의 대표 노드는 8자의 중심이다. 들어오는 간선과 나가는 간선이 모두 2개 이상이다(파란색)
이와 다르게 새로 추가된 노드는 어떤 특징이 있냐면, 나가는 간선만 여러 개고, 들어오는 간선은 존재하지 않는다(빨간색)
이때 새로 추가된 노드 4번에서 나오는 간선의 수는 전체 그래프의 개수와 동일하다는 것을 알 수 있다.
그럼 도넛 그래프의 개수는 전체 그래프 개수에서 막대그래프 개수, 8 자 그래프 개수를 뺀 것과 동일하다.
이러한 특징을 사용해서 각 그래프의 대표 노드들만 찾아서 개수를 갱신하면 정답을 찾을 수 있는 것이다.
🔹 정답 코드
import java.util.*;
class Solution {
public int[] solution(int[][] edges) {
// 각 노드의 들어가는 간선, 나오는 간선 수 저장하는 map
Map<Integer, int[]> nodes = new HashMap<>();
int extraNode = -1; // 추가된 노드
int doughnut = 0; // 도넛 그래프 개수
int stick = 0; // 막대 그래프 개수
int figure8 = 0; // 8자 그래프 개수
// 1단계: 각 노드의 간선 개수 계산
for( int[] edge: edges ){
int from = edge[0];
int to = edge[1];
if(!nodes.containsKey(from)){
nodes.put(from, new int[]{0,0});
}
if(!nodes.containsKey(to)){
nodes.put(to, new int[]{0,0});
}
nodes.get(from)[0]++;
nodes.get(to)[1]++;
}
// 2단계: 노드를 탐색하며 각 그래프의 '핵심 노드' 찾으면 개수 갱신
for( int key : nodes.keySet()){
int[] count = nodes.get(key);
// 나가는 간선이 2개 이상이고, 들어오는 간선이 없을 경우
// = 생성한 정점
if(count[0] >= 2 && count[1] == 0) {
extraNode = key;
}
// 나가는 간선이 없고, 들어오는 간선이 있을 경우
// = 막대 그래프
else if(count[0] == 0 && count[1] > 0) {
stick++;
}
// 들어오는 것과 나가는 것이 각 2개 이상일 경우
// = 8자 그래프
else if(count[0] >= 2 && count[1] >= 2) {
figure8++;
}
}
// 추가한 노드에서 나오는 정점의 개수 = 전체 그래프의 수
// 전체 그래프의 수에서 stick, figure8 빼면 도넛 그래프의 수
doughnut = nodes.get(extraNode)[0] - stick - figure8;
return new int[]{ extraNode, doughnut, stick, figure8 };
}
}
⌛️ 복잡도 계산
노드의 개수가 N일 때,
- 시간 복잡도 : O(N)
맵을 순회하기 때문에 맵의 개수(N)만큼의 시간이 소요된다.
- 공간 복잡도: O(N)
맵의 크기는 노드의 개수와 동일하다.
'Study > JAVA' 카테고리의 다른 글
| [JAVA] 백준 #9663 N-Queen | Back Tracking | 시간 복잡도 최적화 (0) | 2024.06.28 |
|---|---|
| [JAVA] 알고리즘 스터디 7주차 공통과제: 2022 KAKAO 양궁대회 | 테스트케이스 8번 9번 오답 반례 및 예외처리 (0) | 2024.05.31 |
| [JAVA] 백준 #1932 정수 삼각형 | Dynamic Programming | DFS 시간 초과 해결 방법 | 예외 처리 구현 (0) | 2024.05.16 |
| [JAVA] 알고리즘 스터디 4주차 공통과제: KAKAO 택배 배달과 수거하기 📦 | 배열 풀이 (0) | 2024.05.10 |
| [JAVA] 백준 #5430 AC | 덱 Deque | 시간 초과 해결 방법 | 예외 처리 구현 (0) | 2024.05.09 |