백준 11724번 연결 요소의 개수 파이썬 DFS

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

답안 (PyPy3)

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

n, m = map(int, input().split())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)

for i in range(m):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()
    
visited[0] = True # default 값
result = 0
while (visited.count(True)) < (n+1):
    if False in visited:
        v = visited.index(False)
        dfs(graph, v, visited)
        result += 1
    else:
        break
        
print(result)

 

---

 

연결요소들의 각각 개수를 구하는게 문제인데,

나는 반복문과 visited를 이용하여 개수를 세었다.

result = 0
while (visited.count(True)) < (n+1): # 모두 방문했으면 반복문 종료
    if False in visited:
        v = visited.index(False)
        dfs(graph, v, visited)
        result += 1
    else:
        break                        # visited 원소가 다 True면 종료

파이썬에서 index 함수는 중복된게 있으면 가장 앞에 있는 원소의 인덱스를 출력하게 된다.

ex ) x = ['가','나','나','다'] 

이 리스트에서 x.index('나') 를 입력하면 

>>> 1 이 출력된다

따라서 순차적으로 방문 안한 노드를 방문하게 해준다.

.

.

visited 에서 방문 안한 노드(False)를 계속 반복 순환해 주면서 dfs와 순차적 탐색을 동시에 진행을 해준다.

자연스럽게 세는 것도 가능하여 이렇게 코드를 짰다.

python3 에는 루프도는데 시간이 오래 걸려 시간초과가 떴지만

PyPy3는 성공을 했다. (메모리 엄청 많이 쓰네.. ㅎ)