반응형
백준 2606 문제입니다.
https://www.acmicpc.net/problem/2606
문제 보기의 그래프를 1을 중심으로 다시 그려보면 이와 같아집니다. 1번 컴퓨터가 바이러스가 걸렸을 때, 같이 걸린 컴퓨터의 수를 구하는 문제였습니다.
입력
문제의 입력은 [ [ ] , [ 2 , 5 ] , [ 1 , 3 , 5 ] , [ 2 ] , [ 7 ] , [ 1 , 2 , 6 ] , [ 5 ] , [ 4 ] ] 이와 같이 이차원 배열의 형태로 받을 예정입니다.
7
6
1 2
2 3
1 5
5 2
5 6
4 7
출력
4
저는 bfs를 사용하여 문제를 해결했습니다. bfs나 dfs 둘 중 하나 편하신 것을 골라서 문제 푸시면 됩니다.
computer = int(input())
n = int(input())
node_visited = [[] * _ for _ in range(computer + 1)]
for i in range(n):
a, b = map(int, input().split())
node_visited[a].append(b)
node_visited[b].append(a)
def bfs(node_visited,start):
visited, need_visited = [], []
need_visited.append(start)
while need_visited:
node = need_visited[0]
del need_visited[0]
if node not in visited:
visited.append(node)
need_visited.extend(node_visited[node])
return visited
print(len(bfs(node_visited,1)) - 1)
extend() 함수는 [1, 2, 3] 과 같이 리스트 형태로 존재하여도 리스트 안에 넣을 때, 1, 2, 3 의 형태로 분리되어 넣어주는 함수입니다.
append() 함수는 [1, 2, 3] 이면 [1, 2, 3] 으로 삽입됩니다.
반응형
'🔑알고리즘 > baekjoon' 카테고리의 다른 글
백준 1303 : 전투 파이썬 문제 풀이(bfs 알고리즘 사용) (0) | 2022.08.24 |
---|---|
백준 1012 : 유기농 배추 파이썬 풀이(bfs 알고리즘) (0) | 2022.08.21 |
백준 16435 : 스네이크 버드 파이썬 정답 풀이 (0) | 2022.08.04 |
백준 10974 : 모든 순열 파이썬 정답 풀이 (0) | 2022.08.03 |
백준 2309 : 일곱 난쟁이 파이썬 정답 풀이 (combinations의 활용) (0) | 2022.08.03 |