정수 리스트 sticks가 주어집니다. 각 요소는 양쪽 끝의 숫자(1~6)를 가진 막대 하나를 나타냅니다. 두 막대의 끝 숫자가 같으면 연결할 수 있으며, 연결된 막대의 양 끝은 남은 숫자가 되고 길이는 늘어납니다. 만들 수 있는 가장 긴 막대기의 길이를 구하는 문제입니다.
문제 이해하기
예를 들어 sticks = [[2, 3], [2, 4], [3, 5], [6, 6]]인 경우:
[2, 3]과[2, 4]를 2로 연결 →[3, 4](길이 2)[3, 4]와[3, 5]를 3으로 연결 →[4, 5](길이 3)[6, 6]은 혼자 남음 (길이 1)
최장 길이는 3입니다.
해결 접근법: DFS + 백트래킹
각 막대를 그래프의 간선으로, 끝 숫자(1~6)를 정점으로 모델링합니다. 모든 정점에서 시작해 DFS로 탐색하며, 방문한 간선(막대)은 재방문하지 않도록 백트래킹으로 관리합니다.
알고리즘 단계
- 그래프 구성: 각 막대 인덱스를 양쪽 끝 정점에 매핑
- DFS 탐색: 현재 정점에서 연결된 미방문 간선들을 따라 재귀 호출
- 백트래킹: 재귀 복귀 시 방문 표시 제거
- 최댓값 갱신: 모든 시작 정점에서 탐색한 최대 깊이 기록
파이썬 구현
from collections import defaultdict
class Solution:
def solve(self, sticks):
def dfs(node, edge_idx, visited):
if edge_idx is not None:
if edge_idx in visited:
return 0
visited.add(edge_idx)
res = 0
for e_idx in g[node]:
# 현재 간선의 다른 쪽 끝점 찾기
n_node = sticks[e_idx][0] if sticks[e_idx][1] == node else sticks[e_idx][1]
res = max(res, 1 + dfs(n_node, e_idx, visited))
if edge_idx:
visited.remove(edge_idx)
return res
# 막대를 튜플로 변환 (불변성 보장)
sticks = [(s[0], s[1]) for s in sticks]
vertices = set()
g = defaultdict(set)
# 그래프 구성: 정점 → 연결된 간선 인덱스 집합
for i, edge in enumerate(sticks):
g[edge[0]].add(i)
g[edge[1]].add(i)
vertices.add(edge[0])
vertices.add(edge[1])
res = 0
for v in vertices:
res = max(res, dfs(v, None, set()))
# 간선 수 = 막대 수, 길이는 간선 수와 동일하므로 -1 불필요
# (원본 코드는 정점 수 기준이었음)
return res
# 실행 예시
ob = Solution()
sticks = [
[2, 3],
[2, 4],
[3, 5],
[6, 6]
]
print(ob.solve(sticks)) # 출력: 3
코드 핵심 포인트
- defaultdict(set): 정점별 연결 간선 인덱스 저장, 중복 방지
- visited 집합: 현재 경로에서 사용 중인 간선 추적
- 백트래킹:
visited.remove(edge_idx)로 다른 경로 탐색 가능하게 함 - 시작점 전체 탐색: 모든 정점에서 DFS 시작해 최장 경로 보장
시간 복잡도
- O(V + E) 그래프 구성
- O(E × 2^E) 최악의 경우 (모든 간선 조합 탐색)
- 실제로는 막대 끝이 1~6으로 제한돼 상수 시간에 가까움
입력/출력 예시
| 입력 | 출력 |
|---|---|
[[2, 3], [2, 4], [3, 5], [6, 6]] | 3 |