[백준/Python] 결혼식

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

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. 결과값을 출력한다.