백준 11724번: 큐와 그래프 - 파이썬(DFS/BFS)

기본적인 탐색문제인 듯 하다.

이 문제는 DFS로 풀 수 있는데 푸는 방법을 굳이 나눠보자면 인접행렬과 인접리스트 방식으로 풀 수 있다.

이 차이는 그래프를 표현하는 방식의 차이일뿐 본질적인 차이는 없다.

표현 방식에 따라서 코딩을 해주면 된다.

나는 인접행렬 형식으로 풀어보았다.

인접리스트 방식으로 푼 풀이가 궁금하신 분들은 https://hjp845.tistory.com/33 여기 블로그에 코드가 있으니 참고하면 된다.

 

그러나 알고리즘이 아닌 다른 부분에서 좀 해맸다.

 

1. sys.setrecursionlimit(10000)

재귀를 사용할 땐 항상 재귀의 깊이를 넉넉하게 설정해주는 것을 잊지 말아야 한다.

이걸 안해주면 런타임에러(recursuionerror)가 뜬다.

 

2. sys.stdin.readline().split()

위의 문제를 해결하고도 계속해서 시간초과가 떠서 알고리즘만 한참을 보면서 고민을했다.

이전에 사용했던 입력코드는 input()이었는데 이것보다 sys.stdin.readline()이 코드가 더 빨리 입력값을 받는다고 한다.

시간초과가 뜰때는 종종 이 코드로 해결되기도 한다.

# 11724번: 연결 요소의 개수

import sys
sys.setrecursionlimit(10000)

n,m = map(int,sys.stdin.readline().split())

def dfs(v):
    visited_dfs[v] = 1
    for i in graph[v]:
        if visited_dfs[i] == 0 and graph[v][i]:
            dfs(i)

graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u][v] = graph[v][u] = 1

visited_dfs = [0]*(n+1)

count = 0
for i in range(1, n+1):
    if visited_dfs[i] != 1:
        dfs(i)
        count += 1

print(count)