[구름톤 챌린지] 작은 노드(day 14)

 
https://level.goorm.io/exam/195696/%EC%9E%91%EC%9D%80-%EB%85%B8%EB%93%9C/quiz/1

구름LEVEL

 
요즘 매일마다 한문제씩 풀며 머리를 식히고는 있지만 그냥 풀면 재미가 없으니까 chatGPT에게 문제를 풀도록 시켜보자.
 

 

 
문제가 설명을 꼬아놓지는 않았으니 간단히 요약정리해서 물어보자.
 

from collections import defaultdict

def dfs(graph, node, visited):
    visited[node] = True
    next_nodes = graph[node]
    
    smallest_next = float('inf')
    for next_node in next_nodes:
        if not visited[next_node]:
            smallest_next = min(smallest_next, next_node)
    
    if smallest_next != float('inf'):
        dfs(graph, smallest_next, visited)

def main():
    n, m, k = map(int, input().split())
    
    graph = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [False] * (n + 1)
    dfs(graph, k, visited)
    
    visited_count = sum(visited) - 1  # Exclude the starting node
    last_node = visited.index(True, 1)  # Find the index of the last visited node
    
    print(visited_count, last_node)

if __name__ == "__main__":
    main()

defaultdict와 같은 꽤나 고급진 구문을 사용하는 걸 보니 확실히 나보단 나은 거 같지만 구름톤에서는 재귀함수를 싫어하는 듯하니 dfs를 스택으로 구현하도록 시켜보았다.
 

from collections import defaultdict

def dfs(graph, start):
    visited = [False] * (len(graph) + 1)
    stack = [start]
    visited[start] = True
    
    while stack:
        current_node = stack.pop()
        next_nodes = graph[current_node]
        
        smallest_next = float('inf')
        for next_node in next_nodes:
            if not visited[next_node]:
                smallest_next = min(smallest_next, next_node)
        
        if smallest_next != float('inf'):
            stack.append(smallest_next)
            visited[smallest_next] = True

    return visited

def main():
    n, m, k = map(int, input().split())
    
    graph = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited = dfs(graph, k)
    
    visited_count = sum(visited) - 1  # Exclude the starting node
    last_node = visited.index(True, 1)  # Find the index of the last visited node
    
    print(visited_count, last_node)

if __name__ == "__main__":
    main()

다음과 같은 코드를 제출했지만 교묘한 오류가 몇 가지 있기 때문에 그냥 사람의 뇌를 사용해보자.
 
 
 

# 수정본

from collections import defaultdict

def dfs(graph, start):
    visited = [False] * (max(graph) + 1) ##
    #len이 아니라 max함수를 사용
    
    stack = [start]
    visited[start] = True
    
    while stack:
        current_node = stack.pop()
        next_nodes = graph[current_node]
        
        smallest_next = float('inf')
        for next_node in next_nodes:
            if not visited[next_node]:
                smallest_next = min(smallest_next, next_node)
        
        if smallest_next != float('inf'):
            stack.append(smallest_next)
            visited[smallest_next] = True

    return visited, current_node ##
    #visited뿐만 아니라 마지막 노드도 튜플로 묶어서 반환

def main():
    n, m, k = map(int, input().split())
    
    graph = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited, last_node = dfs(graph, k) ##
    # last_node를 dfs함수의 리턴값에서 정의
    
    visited_count = sum(visited) ##
    # sum(visited) - 1 이 아니라 sum(visited)
    
    print(visited_count, last_node)

main() ##
# main 함수는 그냥 호출

 

덕분에 머리를 싸맬 일이 줄어들어서 좋다.

끝