[CodeTree/Python] 연결된 그래프 2

문제

연결된 그래프 2

n개의 정점으로 이루어진 그래프에서 가장 많은 정점으로 갈 수 있는 노드들의 번호를 구하는 프로그램을 작성해보세요.

각 간선은 양방향이 아닙니다.

 

입력 형식

첫 번째 줄에 n과 m이 공백을 사이에 두고 주어집니다.

두 번째 줄 부터 m개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호가 A B 형식으로 주어집니다. 이 형식은 A는 B로 바로 갈 수 있다는 뜻입니다.

• 1 ≤ n ≤ 1,000
• 1 ≤ m ≤ 10,000

출력 형식

가장 많은 정점으로 갈 수 있는 노드를 출력하세요. 만약 그런 노드가 여러개라면 번호를 오름차순으로 공백을 사이에 두고 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

 

1. 인접 리스트 생성

n, m = map(int, input().split())

li = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    li[a].append(b) # 단방향 처리

 

    * (주의) 각 간선은 양방향이 아니므로 단방향만 처리해 주어야 한다.

 

 

2-1. 재귀 함수를 사용하여 풀이

# 방문 처리를 위한 리스트 생성
visit = [False] * (n + 1)

# 재귀 함수 생성
def dfs(node):
    visit[node] = True 
    for i in li[node]:
        if not visit[i]:
            dfs(i) 
        
result = [[] for _ in range(n + 1)] # 각 노드별 방문 횟수를 담을 리스트 생성

for i in range(n + 1):
    dfs(i)
    result[i].append((sum(visit) - 1))
    visit = [False] * (n + 1) # 모든 케이스를 처리해야하므로, 방문 표시 초기화

ans = []
for i in range(n + 1):
    if result[i] == max(result): #반복문을 돌면서 result의 최대값과 일치할 시, i를 정답 리스트에 추가
        ans.append(i)

for i in ans:      
    print(i, end = ' ')

 

    처음에는 형태가 단순하게 빠지는 재귀 방식으로 풀이를 진행했다. 다른 문제뿐만이 아니라 생각해 보니까 함수 안에서 방문 표시를 초기화할 수도 있었는데 푸는데 급급하다 보니(...) 아무튼, 이 문제는 각 정점에서 방문할 수 있는 정점의 개수를 모두 구해야 하므로(max값이 필요함) 위 방식으로 풀게 되면 재귀 함수를 n회를 호출해야 한다. 그래서 정답으로는 넘어갔는데, 오버헤드가 증가해서? 실행 시간이 엄청 길어진 것 같다.

 

2-2. 스택을 사용하여 풀이

# 스택으로 처리
def dfs(i):
    visit = [False] * (n + 1)
    stack = [i]
    count = 0

    while stack:
        node = stack.pop()
        if not visit[node]:
            visit[node] = True
            for j in li[node]:
                if not visit[j]:
                    stack.append(j)
            if node != i:
                count += 1
    return count

result = [[] for _ in range(n + 1)] # 각 노드별 방문 횟수를 담을 리스트 생성

for i in range(n + 1):
    result[i].append(dfs(i))

ans = []
for i in range(n + 1):
    if result[i] == max(result): #반복문을 돌면서 result의 최대값과 일치할 시, i를 정답 리스트에 추가
        ans.append(i)

for i in ans:      
    print(i, end = ' ')

 

    그래도 기왕 공부하기 시작한 거, 내 생각이 맞는지 확인해볼 겸 공부도 좀 더 할 겸 스택으로도 풀어봤다. 이번엔 함수 안에서 방문 표시랑 카운트 초기화까지 다 넣고 돌렸다. 리턴 값도 그냥 카운트로 지정해줬다. 아무튼 실행 시간도 메모리도 엄청 줄었다. 모든 노드를 돌려봐야 하는 경우엔 스택으로 푸는 게 확실히 이득일 것 같다. 더 괜찮은 방법이 물론 있을 수 있겠지만 지금 내 지식 상태로는 이게 최선인듯~!

 

시간 엄청 줄었다. 백퍼 초과 났음