[Baekjoon] 5567_결혼식

Silver II

문제(출처: https://www.acmicpc.net/problem/5567)

---

<결혼식>

문제 

 

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

 

출력 

 

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

 

 

문제 풀이

- my solution

import sys

def friend(graph, start):
    queue=graph.get(start) #자신의 친구
    visited=[start]

    while queue:
        a=queue.pop(0)
        visited.append(a) # 자신의 친구
        visited+=graph.get(a) # 친구의 친구

    result=len(set(visited))-1 # 결혼식에 초대할 사람의 수
    return result


if __name__=='__main__':
    n=int(input())
    m=int(input())

    graph={}
    for i in range(n):
        graph[i+1]=[]

    for i in range(m):
        x,y=map(int, sys.stdin.readline().split())
        graph[x].append(y)
        graph[y].append(x)

    result=friend(graph, 1)
    print(result)

 

풀면서도 이상했지만 다 풀고도 이상하다고 생각하는 문제이다. 그래프 탐색 문제라 보고 들어갔지만 난... 그렇게 풀지 못한 것 같기 때문이다. 깊이를 세서 깊이가 3 이상 일 때 break를 걸고 싶다는 것이 첫 번째 생각이었으나, 생각대로 하지 못하고 쉬운 방법으로 가버렸다.

다른 사람 풀이를 봐도 음... 아직 잘 모르겠다. 그래서 일부러 함수 명도 friend로 지었다...

 

• friend
  - 자신의 친구를 queue에 넣고, visited에는 start만 넣음
  - queue가 빌 때까지 반복: 첫 번째를 pop 하고 그 값과 그래프에서 그 값을 key값으로 한 value를 추가
  - result: visited를 set 하여 중복을 없앤 후 시작 정점인 1을 뺀 길이
• main
  - 입력
  - 양방향으로 추가

 

내가 생각한 풀이는 위와 같다. 친구의 친구까지 찾는 것이므로, 처음에 나의 친구를 queue에 넣고 queue에 든 값에 대해서만 한 번 더 찾아주면 친구의 친구를 다 찾을 수 있는 것이 아닌가...! ㅜ_ㅜ 왜 이렇게 쉽게 풀면 안 되는 건가요... ㅠㅠ

---

생각🤔

 

 

---