[백준][파이썬]11724번: 연결 요소의 개수

문제 출처 : www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

내 풀이

1차 (시간초과)

n, m = map(int, input().split())

arr = [[0] * n for _ in range(n)]
visit = [0] * n
answer = 0

def bfs(num):
    k = [num]
    while k:
        a = k.pop(0)
        for i in range(n):
            if arr[a][i] == 1 and visit[i] == 0:
                k.append(i)
                visit[i] = 1
      
for i in range(m):
    x, y = map(int, input().split())
    arr[x - 1][y - 1] = 1
    arr[y - 1][x - 1] = 1

for i in range(len(visit)):
    if visit[i] == 0:
        bfs(i)
        answer += 1
        
print(answer)

2차원 배열에 연결된 값들의 위치에 1을 넣어주고 bfs를 돌리면서 방문체크를 해주는 식으로 코드를 짰다.

2차 (통과)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

arr = [[0] * n for _ in range(n)]
visit = [0] * n
answer = 0

def bfs(num):
    k = [num]
    while k:
        a = k.pop(0)
        for i in range(n):
            if arr[a][i] == 1 and visit[i] == 0:
                k.append(i)
                visit[i] = 1
       
for i in range(m):
    x, y = map(int, input().split())
    arr[x - 1][y - 1] = 1
    arr[y - 1][x - 1] = 1

for i in range(len(visit)):
    if visit[i] == 0:
        bfs(i)
        answer += 1
        
print(answer)

input을 sys로 바꾸어서 실행해보니 합격이 떴다.

 

어지간하면 항상 sys.stdin.readline()을 사용하도록 습관을 들여야겠다.