[백준/Python] 결혼식

[백준/Python] 결혼식

728x90

https://www.acmicpc.net/problem/5567

n = int(input()) m = int(input()) graph = [[] for _ in range(n+1)] visited = [0] * (n+1) # 방문 확인 및 관계 구분 리스트 # 친구 관계 입력받기 for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # BFS 수행 메서드 def bfs(start): queue = [start] visited[start] = 1 while queue: v = queue.pop(0) for i in graph[v]: # 현재 노드의 인접 노드 확인 if not visited[i]: queue.append(i) visited[i] = visited[v] + 1 # 상근이와의 관계 구분을 위해 +1 return visited.count(2) + visited.count(3) # 1: 본인, 2: 친구, 3: 친구의 친구 print(bfs(1))

1. graph 와 visited 를 생성하고 친구 관계를 입력받는다.

2. BFS를 수행한다.

2-1. 시작 노드를 큐에 담고 시작 노드를 방문 처리 해준다. 시작 노드는 본인이므로 값을 1로 해준다.

2-2. 큐에 값이 없을 때까지 다음 과정을 반복한다.

2-3. 큐에서 pop 하여 현재 노드를 가져온 후 현재 노드의 인접 노드를 확인한다.

2-4. 인접 노드를 아직 방문하지 않았다면 큐에 추가하고 방문 처리를 해준다. 이 때 상근이와의 관계 구분을 위해 현재 노드의 방문값에 +1 해준다.

2-5. 큐에 값이 없으면 반복문을 빠져나와 결과값을 리턴한다. 친구와 친구의 친구까지만 초대할 수 있으므로 visited에서 2와 3의 개수를 리턴한다.

3. 결과값을 출력한다.

728x90

from http://soohyun6879.tistory.com/229 by ccl(A) rewrite - 2021-11-12 12:00:41