상원이의 생일파티 Python(SW Expert Academy, SWEA)

난이도 : D5

문제번호 : 5521

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

상원이의 생일 파티가 곧 열린다! 그렇기에 상원이는 반 친구들에게 생일 파티 초대장을 주려고 한다. 그러나 파티가 어색하게 되는 것을 원치 않는 상원이는 모든 친구들에게 초대장을 줄 생각이 없다. 같은 반에 있지만, 서로 친한 친구가 아닐 수도 있기 때문이다. 상원이는 우선 자신과 친한 친구들에게는 모두 초대장을 주기로 했다. 여기에 더해서 친한 친구의 친한 친구인 경우에도 초대장을 주기로 했다. 총 몇 명의 친구들에게 초대장을 주어야 하는지 구하는 프로그램을 작성하라. 상원이의 반에는 N명이 있으며, 각 학생들은 1번에서 N번까지의 번호가 붙어 있다. 여기서 1번 학생이 상원이다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에 두 정수 N, M ( 2 ≤ N ≤ 500, 1 ≤ M ≤ 10^4 ) 이 공백으로 구분되어 주어진다. M은 친한 친구 관계의 수 이다. 다음 M개의 줄의 각 줄에는 두 정수 a, b (1 ≤ a ＜ b ≤ N) 이 주어진다. 이는 a번 학생과 b번 학생이 서로 친한 친구 관계에 있다는 의미이다.

출력

각 테스트 케이스마다 #T를 출력하고 한 칸을 띄운 후, 각 테스트 케이스마다 상원이의 생일 파티 초대장을 받는 친구의 수를 출력한다. *상원이의 친구가 없을 수도 있다는 점에 유의해야 한다. 그리고 상원이는 초대장을 받는 사람에 속하지 않는다.

예시

입력	출력
2        6 5      2 3      3 4 4 5 5 6 2 5 6 5      1 2 1 3 3 4 2 3 4 5	#1 0 #2 3

---

2. 문제풀이

그래프를 문제이다. 자신의 친한친구와 친한친구의 친한친구까지만 초대장을 준다고 한다. 감염문제와 비슷한데 최대 감염횟수가 2(자기친구, 친구의 친구)이된다. 이런 문제는 BFS를 이용하여 풀면된다. 감염횟수가 남아있다면 자기와 연결된 인원을 큐에 넣어주는 형식으로 풀어나갔다.

---

3. 소스코드

# D5 5521 상원이의 생일파티
from collections import deque
 
# bfs를 이용하여 탐색
def bfs(queue):
    global answer
    # 큐가 빌대까지
    while len(queue):
        # 탐색할 인덱스와 깊이
        idx, depth = queue.popleft()
        # 탐색 시작
        for i in tree[idx]:
            # 아직 초대장을 안줬다면
            if visited[i]:
                # 초대장 챙겨주고
                visited[i] = 0
                answer += 1
                # 친한친구의 친구인지 확인
                # 친한친구의 친구까지니까 깊이를 한단계만 갈수있도록 설정
                if depth < 1:
                    queue.append((i, depth+1))
 
 
for t in range(int(input())):
    answer = 0
    # 입력받고
    N, M = map(int, input().split())
    # 트리는 연결리스트로 표현하고
    tree = [[] for _ in range(N+1)]
    # 방문체크용도 만들어 주고
    visited = [1] * (N+1)
    # 트리 연결도 해주고
    for _ in range(M):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    # 앞에서 부터 꺼낼꺼니까 디큐 사용
    queue = deque()
    # 1번이 상원이니까 1번이랑 깊이 0으로 추가
    queue.append((1, 0))
    # 사용했다고 표시하고
    visited[1] = 0
    # 탐색시작
    bfs(queue)
    # 결과값 출력
    print('#{} {}'.format(t+1 , answer))