백준 5237번
https://www.acmicpc.net/problem/5237

문제

후기

⏰ 풀이시간 20분 ++⏰

맞힌 사람이 많지 않은 그래프 문제를 풀기 위해 풀은 사람이 적은 순으로 정렬해서

찾은 문제의 5번째다. 문제의 결론을 이야기 하자면,

여러 테스트 케이스가 주어지는데, 그래프의 모든 연결요소들이
서로 연결되어 있는 그래프면 Connected, 그렇지 않다면 Not connected를 출력하는 문제다.

매 테스트케이스 마다 list가 주어지는데, 그래프의 정점 숫자를 N으로, 연결요소의 숫자를 K로

선언했고, 연결요소는 list 슬라이싱으로 입력을 정리했다.

list를 순회하며 길이가 2가 됐을때 [0,1][1,2] 등등..

해당 리스트 요소들을 연결요소 처리하며 문제를 접근하여 풀게 되었다.

나의 풀이

import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**7)

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

T = int(input())
for _ in range(T):
    li = list(map(int,input().split()))
    N = li[0] # 정점수
    K = li[1] # 연결요소의 수
    li = li[2:] #연결요소 리스트 

    graph = [[] for _ in range(N)]
    visited= [False] * (N)
    connect =[]
    for i in li: #list를 돌며
        connect.append(i) 
        if len(connect)==2: #list의 길이가 2가 되면 해당 연결요소를 그래프에 추가한다. 
            graph[connect[0]].append(connect[1])
            graph[connect[1]].append(connect[0])
            connect = []
    
    dfs(0) #모든 연결요소가 추가됐으면 dfs 시작

    if False in visited: #연결되지 않은 정점이 하나라도 있으면
        print("Not connected.") #연결되지않음
    else: #모두 연결되어있으면
        print("Connected.") #연결됨 출력