9. 그래프 - 깊이 우선 탐색(DFS, Depth First Search)

콜라츠 추측 - https://school.programmers.co.kr/tryouts/85936/challenges

def solution(num):
    if num == 1: return 0
    cnt = 0
    while cnt <= 500 and num != 1:
        if num % 2 == 0: # 짝수
            num //= 2
        else:
            num = 3 * num + 1
        cnt += 1
    if num != 1: return -1
    return cnt

 

---

여행 경로 - https://school.programmers.co.kr/tryouts/85937/challenges

dfs 사용 → 불가능 경로도 존재하므로, 백트래킹 해야함

def dfs(graph, start, path, n):
    if len(path) == n + 1:  # 항공권 모두 사용
        return path
    
    if start not in graph: # 경로 없음
        return None  
    
    for dest, count in graph[start].items():
        if count:  # 항공권이 있는 경우
            graph[start][dest] -= 1  # 항공권 사용 처리
            result = dfs(graph, dest, path + [dest], n)
            if result:
                return result
            graph[start][dest] += 1  # 원상복구
            
def solution(tickets):
    graph = {}
    for (start, end) in tickets:
        if start not in graph:
            graph[start] = {}
        if end not in graph[start]:
            graph[start][end] = 0
        graph[start][end] += 1
    for city in graph: # 알파벳 순 정렬
        graph[city] = dict(sorted(graph[city].items()))
        
    answer = dfs(graph, "ICN", ["ICN"], len(tickets))
    return [key for key in answer]

 

---

네트워크 - https://school.programmers.co.kr/tryouts/85938/challenges

전형적인 dfs문제

def dfs(table, visit, start):
    path = [start]
    while path:
        cur = path.pop()
        if not visit[cur]:
            visit[cur] = 1
        for con in table[cur]:
            if not visit[con] and con not in path: # 새 컴퓨터만 연결
                path.append(con)
    return visit

def solution(n, computers):
    table = dict()
    for i in range(n): # 연결된 컴퓨터만 남김
        con_nums = [idx for idx, value in enumerate(computers[i]) if value == 1 and i != idx]
        table[i] = con_nums
        
    ans = 0
    visit = [0] * n
    start = 0
    while start < n:
        if not visit[start]:
            visit = dfs(table, visit, start)
            ans += 1
        start += 1
    return ans

 

핵심 : 기본 구성 → dfs(graph, 시작점, 기억할 것, …(기타))