[ 5567 ] [ DFS ] 결혼식

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

5567번: 결혼식

---

풀이 과정

---

1. 입력받은 친구 번호에 맞추어서 그래프를 구성한다.

   • graph[번호]에 해당 번호의 친구들을 저장해둔다.

2. 1번부터 DFS를 진행하여 결혼식에 오는 친구들을 방문처리 해준다.

   • DFS의 깊이가 2일때 종료시켜 준다. (친구의 친구까지만 진행하므로)

3. 전체 DFS 과정이 종료되면 VISITED가 TRUE인 개수를 구한 뒤 1을 빼준다.

   • 상근이를 빼주어야 함.

---

소스 코드

---

import sys

input = lambda : sys.stdin.readline().rstrip()

def dfs(graph, visited, person, depth):
    if depth == 2:
        return
    for nx in graph[person]:
        if not visited[nx]:
            visited[nx] = True
        dfs(graph, visited, nx, depth+1)

n = int(input())
m = int(input())
friends = [map(int, input().split()) for _ in range(m)]

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
visited[1] = True

for p1, p2 in friends:
    graph[p1].append(p2)
    graph[p2].append(p1)

dfs(graph, visited, 1, 0)
print(len(list(filter(lambda x:x==True, visited))) - 1)