✅ 들어가기 전에
기존 알고리즘 스터디가 스터디원 과반수 취업이라는 성공적인 결과로 마무리 되고, 한동안 혼자 문제풀이를 진행했습니다. 역시 혼자 문제 푸는 건 재미가 별로 없네요. 새로운 알고리즘 스터디가 시작했습니다.
새로운 알고리즘 스터디는 프로그래머스 플랫폼을 활용해 진행되며, 일주일에 두 문제(LEVEL2, LEVEL3)를 풀이하게 됩니다. 스터디 문제 같은 경우 스터디원들에게 설명하기 전 해당 블로그 포스팅을 통해 풀이 방법을 정리하려 합니다.
또한 혼자 문제를 풀이할 때 하루에 구현 문제 한 문제씩을 풀었었는데, 시간이 나거나 좋은 인사이트가 생긴 경우 해당 문제에 대한 풀이도 포스팅하겠습니다.
🔴 문제 개요
🚀 난이도 : LEVEL2
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 아래 그림 처럼 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.
- 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다.
- 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다.
- 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다.
이때 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.
제한 사항
- 1 ≤ edges의 길이 ≤ 1,000,000
- edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
- 1 ≤ a, b ≤ 1,000,000
- 문제의 조건에 맞는 그래프가 주어집니다.
- 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.
🟠 Solution
1. 생성된 정점 판단
처음 문제를 읽었을 때, 그래프 탐색 및 순회를 통해 그래프를 파악해야 할 것 같았고, 접근 방법이 떠오르지 않아 지레 겁부터 먹었던 것 같습니다. 문제를 꼼꼼히 읽어보니 그래프 별로 정점에 입출력 되는 간선의 수에 특징이 있다는 것을 파악하고, 간선 정보를 바탕으로 그래프를 구분하면 풀이가 가능하다고 생각했습니다.
또한 문제에서 언급하는 생성된 정점 은 각 그래프의 임의의 정점으로 뻗는 간선밖에 존재하지 않습니다. 또한 그래프는 2개 이상 존재하므로 생성된 정점에서 뻗는 간선도 2개 이상일 것입니다. 즉, 뻗는 간선만 존재하며, 뻗는 간선이 2개 이상인 정점이 생성된 정점입니다. (앞으로 뻗는 간선 : in, 들어오는 간선 : out이라 표현)
def solution(edges):
# 생성된 정점 찾기
st_dict = defaultdict(list)
en_dict = defaultdict(int)
for st, en in edges:
st_dict[st].append(en) # 뻗는 간선 정보
en_dict[en] += 1 # 들어오는 간선 수
for st, lst in st_dict.items():
# 생성된 정점 판단
if len(lst) >= 2 and st not in en_dict:
root = st
answer = [root, 0, 0, 0] # [정점, 도넛, 막대, 8자]
...in과 out의 정보를 각각 defaultdict에 저장합니다. out은 앞으로 그 수만 활용하게 될 것이므로 int형으로 선언하여 개수를 세어줬습니다. 그리고 생성된 정점을 파악했습니다.
2. 각 그래프의 정점 집합 찾기
각 그래프 내 정점의 in과 out을 바탕으로 그래프 유형을 판단하기로 했습니다. 따라서 각 그래프 내 정점 집합을 분리해주어야 합니다.
이를 위해서 생성된 정점의 in과 연결된 정점을 활용할 수 있습니다. 해당 정점들을 시작으로 그래프 탐색 알고리즘(BFS, DFS)를 실행하면, 연결된 정점들을 파악할 수 있습니다. 답을 도출하는 과정에서 생성된 정점의 정보는 이 과정 외에 더 이상 필요 없으므로, 생성된 정점에서 뻗은 간선의 정보를 제거해주었습니다.
def solution(edges):
...
# 생성된 정점에서 뻗은 간선 제거
for en in st_dict[root]:
en_dict[en] -= 1
# 그래프 탐색
for other_root in st_dict[root]:
idx = validate(other_root, st_dict, en_dict)
answer[idx] += 1
return answer
def validate(root, st_dict, en_dict):
nodes = {root}
queue = deque([root])
# BFS로 그래프에 포함된 정점 찾기(DFS 재귀 활용시 최대 재귀 깊이 에러)
while queue:
cur = queue.popleft()
for v in st_dict[cur]:
if v not in nodes:
nodes.add(v)
queue.append(v)
...그래프 탐색에서는 BFS를 활용합니다. DFS 활용 시, 특정 테스트케이스에서 max recursion error가 발생하는 것을 확인할 수 있었습니다.
3. 그래프 판단하기
이제 구분된 집합 내 정점의 in과 out을 통해 그래프의 유형을 구분할 수 있습니다. 저는 그래프 유형 별 특징이 다음과 같음을 파악했습니다.
- 도넛 그래프 : 각 정점의
in : 1 / out : 1 - 막대 그래프 : 특정 정점이
in : 1 / out : 0orin : 0 / out : 1 - 8자 그래프 : 특정 정점의
in : 2orout : 2
이를 바탕으로 그래프를 판단하는 로직을 구성하면 다음과 같습니다.
def validate(root, st_dict, en_dict):
"""
root로 시작하는 그래프 내 정점을 찾고, 해당 그래프의 유형을 판별하여 반환
"""
...
# 그래프 판별
for node in nodes:
# 도넛 그래프의 모든 정점은 in 1 / out 1
if not (len(st_dict[node]) == 1 and en_dict[node] == 1):
# in, out 중 하나라도 두 개 이상이면 8자
if len(st_dict[node]) >= 2 or en_dict[node] >= 2:
return 3
# in 1 / out 0 or in 0 out 1 인 경우 막대
else:
return 2
return 1도넛과 8자 그래프의 기준이 비교적 명확하므로 먼저 조건을 판단해주고, 모두 아닌 경우 막대 그래프로 판단하도록 로직을 구성했습니다.
전체 코드
from collections import defaultdict, deque
from typing import List, Dict
def validate(root: int, st_dict: Dict[int,int], en_dict: Dict[int, int]) -> int:
"""
root로 시작하는 그래프 내 정점을 찾고, 해당 그래프의 유형을 판별하여 반환
"""
nodes = {root}
queue = deque([root])
# BFS로 그래프에 포함된 정점 찾기(DFS 재귀 활용시 최대 재귀 깊이 에러)
while queue:
cur = queue.popleft()
for v in st_dict[cur]:
if v not in nodes:
nodes.add(v)
queue.append(v)
# 그래프 판별
for node in nodes:
# 도넛 그래프의 모든 정점은 in 1 / out 1
if not (len(st_dict[node]) == 1 and en_dict[node] == 1):
# in, out 중 하나라도 두 개 이상이면 8자
if len(st_dict[node]) >= 2 or en_dict[node] >= 2:
return 3
# in 1 / out 0 or in 0 out 1 인 경우 막대
else:
return 2
return 1
def solution(edges: List[List[int]) -> List[int]:
"""
1. 새로 생성된 정점을 찾는다.
2. 새로 생성된 정점에 연결된 각 그래프의 정점 집합을 찾는다.
3. 집합 내 정점의 in, out 간선 수를 바탕으로 그래프 유형을 파악한다.
"""
# 생성된 정점 찾기
st_dict = defaultdict(list)
en_dict = defaultdict(int)
for st, en in edges:
st_dict[st].append(en)
en_dict[en] += 1
for st, lst in st_dict.items():
if len(lst) >= 2 and st not in en_dict:
root = st
answer = [root, 0, 0, 0] # [정점, 도넛, 막대, 8자]
# 생성된 정점에서 뻗은 간선 제거
for en in st_dict[root]:
en_dict[en] -= 1
# 그래프 탐색
for other_root in st_dict[root]:
idx = validate(other_root, st_dict, en_dict)
answer[idx] += 1
return answer🟡 Solution 2 : 더 명확하게 설명 가능한 풀이
스터디에서 받은 피드백을 바탕으로 위 코드를 더 명확하게 설명 가능한 풀이로 수정할 수 있다는 것을 알았습니다. validate 함수에 대한 수정입니다.
def validate(root: int, st_dict: Dict[int, List], en_dict: Dict[int, int]) -> int:
"""
그래프 내 노드 수와 간선 수를 카운트 하여 그래프 유형을 판단한다.
"""
nodes = set([root])
queue = deque([root])
node_cnt = 0
edge_cnt = 0
# 그래프 순회(BFS)
while queue:
cur = queue.popleft()
# 노드와 간선 수 카운트
node_cnt += 1
edge_cnt += len(st_dict[cur])
for v in st_dict[cur]:
if v not in nodes:
nodes.add(v)
queue.append(v)
# 도넛 조건
if node_cnt == edge_cnt:
return 1
# 8자 조건
elif node_cnt + 1 == edge_cnt:
return 3
# 나머지 막대 조건
else:
return 2문제에는 아래와 같이 명확한 각 그래프 구분 조건이 주어져있습니다.
- 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다.
- 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다.
- 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다.
따라서 그래프 별로 정점 집합을 구분했으므로, 각 그래프의 정점 수와 간선 수를 카운트할 수 있을 것입니다. 이를 통해 문제에서 제시한 조건대로 그래프 유형을 구분할 수 있습니다. 효율성은 별 차이 없지만, 이 풀이가 더 명확하게 설명 가능한 풀이라고 생각이 드네요!
📚 고찰
항상 문제에 답이 있다는 것을 여러 시행착오 끝에 파악하는 것 같습니다. 더 어려운 이론을 배워나갈 수록 쉬운 문제를 어렵게 풀려는 습관이 생기는 것 같습니다. 시간에 쫒겨 조급한 마음에 풀이부터 하려 하지 말고, 항상 문제와 조건을 먼저 주의 깊게 보고, 적절한 풀이에 빠르게 다가가는 것이 제게 필요한 것 같습니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
✏️ Algorithm Study
본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.
