파이썬(Python) 코테 대비 Graph : 백준 11724번 연결 요소의 개수

[시작 체크 리스트]

1. 1시간 지났으나 발상 불가 또는 아예 다른 길
2. 코드 50% 정도 완성
3. 1시간 보다 더 걸려서 코드 완성
4. 코드는 다 돌아가는데 효율성에서 걸림
5. 코드 완성

[완료 후 체크 리스트]

1. 아예 모르겠음
2. 중간 정도 이해함
3. 완벽히 이해함

1. 첫 풀이 (시간오류)

N,M=map(int,input().split())
matrix=[[0]*(N+1)for i in range(N+1)]

for i in range(M):
    a,b=map(int,input().split())
    matrix[a][b]=matrix[b][a]=1
visit_list=[0]*(N+1)

def bfs(v):
    queue=[v]
    while queue:
        v=queue.pop(0)
        for i in range(1,N+1):
            if matrix[i][v]==1 and visit_list[i]==0:
                visit_list[i]=1
                queue.append(i)
answer=0
for i in range(1,N+1):
    if visit_list[i]==0:
        bfs(i)
        answer+=1

기본적인 bfs를 사용하여 경로를 찾아주고, 처음 선택한 정점과 이어져있지 않다면 다시 bfs를 하는 방식을 사용했는데, 예제는 다 통과했지만, 시간 초과나길래 matrix를 써서 그런건가 싶어서 단순하게 리스트로 짜봐야 겠다는 생각을 했다.

2. 둘째 풀이 (시간오류)

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

graph=[[]for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
visit_list=[0]*(N+1)

def bfs(v):
    q=[v]
    while q:
        v=q.pop(0)
        for i in graph[v]:
            if visit_list[i]==0:
                q.append(i)
                visit_list[i]=1

answer=0
for i in range(1,N+1):
    if visit_list[i]==0:
        bfs(i)
        answer+=1

print(answer)

여전히 시간 오류 났다. ㅠㅠ
백준이 프로그래머스 보다 답답한게 그렇다면 정답은 맞는 건지, 단순히 비효율적인건지 확인할 방법이 없다.
사실 이 방식이 자체로는 맞는 건지도 모르겠다.

[구글링 이후]

1. 발상 1 (bfs 이용)

하 ^^ 진짜 개빡친다...
다 맞았는데 원래 백준에서는 input()을 쓰면 자주 시간 초과가 되어서 sys를 자주 쓴다고 한다...
input 부분을 바꿔주니 바로 통과 되었다

2. 코드

import sys

N,M=map(int,sys.stdin.readline().split())

graph=[[]for i in range(N+1)]
for i in range(M):
    a,b=map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit_list=[0]*(N+1)

def bfs(v):
    q=[v]
    while q:
        v=q.pop(0)
        for i in graph[v]:
            if visit_list[i]==0:
                q.append(i)
                visit_list[i]=1

answer=0
for i in range(1,N+1):
    if visit_list[i]==0:
        bfs(i)
        answer+=1

sys.stdout.write(str(answer))

(출처 : https://www.acmicpc.net/problem/11724)