Baekjoon 11724번 연결 요소의 개수

문제

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

걸린 시간

00 : 22 : 54

풀이

Python3

import sys
input = sys.stdin.readline

class Node():
    def __init__(self, v):
        self.vertex = v
        self.link = None

class listGraph():
    def __init__(self):
        self.n = 0 # vertex count
        self.adj_list = []

    # adj_list 의 인덱스를 정점의 번호로 설정
    def insert_vertex(self):
        self.adj_list.append(None)
        self.n += 1

    # v값을 u의 인접 리스트에 삽입
    def insert_edge(self, u, v): 
        new = Node(v)
        if u > self.n-1 or v > self.n-1:
            print("out of area")    
        else:
            new = Node(v)
            new.vertex = v
            new.link = self.adj_list[u]
            self.adj_list[u] = new

def dfs(g, v, visited):
    visited[v] = True
    w = g.adj_list[v]
    while w != None:
        if not visited[w.vertex]:
            dfs(g, w.vertex, visited)
        w = w.link

def find_connected_component(g, visited):
    count = 0
    # 0번 정점 사용하지 않음
    for i in range(1, g.n):
        if not visited[i]:
            count += 1
            dfs(g, i, visited)
    print(count)

if __name__ == "__main__":
    sys.setrecursionlimit(2000)

    N, M = map(int, input().strip().split())    

    g = listGraph()
    for _ in range(0, N+1):
        g.insert_vertex()

    for _ in range(0, M):
        u, v = map(int, input().strip().split())
        g.insert_edge(u, v)
        g.insert_edge(v, u)

    visited = [False for _ in range(0, N+1)]

    find_connected_component(g, visited)

리스트로 구현한 그래프의 소스를 가져다가 사용했다. 문제의 시간제한이 3초로 넉넉해 통과는 했지만 시간, 메모리 측면에서 많이 비효율적이다.

효율적인 풀이

Python3

import sys
input = sys.stdin.readline

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

def find_connected_component(visited):
    count = 0
    # 0번 정점 사용하지 않음
    for i in range(1, len(adj)):
        if not visited[i]:
            count += 1
            dfs(i, visited)
    print(count)

if __name__ == "__main__":
    sys.setrecursionlimit(2000)

    N, M = map(int, input().strip().split())    

    adj = [[] for i in range(0, N+1)]

    for _ in range(0, M):
        u, v = map(int, input().strip().split())
        adj[u].append(v)
        adj[v].append(u)

    visited = [False for _ in range(0, N+1)]

    find_connected_component(visited)

그래프에 대한 이해가 부족하지 않다면 인접 노드를 보관하는 리스트만 하나 두어 그래프를 구현해도 될 것 같다.