백준 9372 : 상근이의 여행

https://www.acmicpc.net/workbook/view/2063

문제집: SW역량테스트 준비 (lcs11244)

1. DFS/BFS 문제의 전형적인 형태?

나는 BFS 로 문제를 풀었다.

평이한 문제. 예전에 풀었던 문제 복습도 한 번 해줌.

https://aeromaster.tistory.com/15

[220806] 백준 11724 : 연결 요소의 개수

2. 전체코드

메모리 : 134324 KB, 시간 : 388 ms, 풀이시간 : 20 min

T = int(input())
result = []
for _ in range(T):
    N, M = map(int, input().split())
    info = [list(map(int, input().split())) for _ in range(M)]
    graph = [[] for _ in range(N + 1)]
    visited = [False for _ in range(N + 1)]
    for x, y in info :
        graph[x].append(y)
        graph[y].append(x)


    def bfs():
        q = [1]
        num = 0
        visited[1] = True
        while q :
            loc = q[0]
            del q[0]
            if visited.count(True) == N : return num
            for x in graph[loc] :
                if not visited[x] :
                    visited[x] = True
                    num += 1
                    q.append(x)
    result.append(bfs())

for number in result :
    print(number)