0~n-1번 지점을 양방향 통로 edges가 연결해요. blocked에 들어 있는 지점은 출발·도착·경유를 모두 할 수 없어요. start에서 이동할 수 있는 서로 다른 지점 수를 구해요. 허용된 출발 지점 자신도 세며 start가 금지되어 있으면 0이에요.
solution(n, edges, blocked, start)가 지점 수를 반환하도록 빈칸을 채워 주세요. 여러 통로와 순환 경로가 있어도 같은 지점을 한 번만 세어요.
매개변수와 반환값
- n은 1
100, 통로 수 m은 0500이에요. 각 통로의 두 끝점은 0~n-1이에요. - 자기 자신으로 가는 통로와 중복 통로도 있을 수 있어요.
- blocked는 서로 다른 지점 번호 0
n개의 리스트이며 start는 0n-1이에요. - 반환값은 도달한 허용 지점 수인 정수예요.
예시
n = 5,edges = [[0, 1], [1, 2], [2, 3], [0, 4]],blocked = [2],start = 0이면 결과는3이에요.n = 3,edges = [[0, 1], [1, 2]],blocked = [0],start = 0이면 결과는0이에요.
실행용 입출력
첫 줄에 n m b start, 다음 m줄에 통로의 두 끝점, 마지막 줄에 blocked b개를 입력해요. b=0이면 마지막 줄은 빈 줄이에요. 결과 하나를 출력해요.
예시 입력
5 4 1 0 0 1 1 2 2 3 0 4 2
예상 결과
3
예시 입력
3 2 1 0 0 1 1 2 0
예상 결과
0
핵심 개념
graph-basic: 인접 리스트graph[node]는 node에서 직접 갈 수 있는 지점들을 담아요. 양방향 통로라 양쪽 리스트에 모두 추가해요. 재귀 visit은 한 지점을 표시하고 연결된 미방문 지점을 계속 확인해요.array-1d:seen[node]는 한 지점의 방문 상태예요. 먼저 방문 표시를 한 뒤 다음 지점을 호출해야 순환 경로도 끝낼 수 있어요.conditionals: 미방문 여부와 통행 허용 여부를 동시에 확인해요.
set(blocked)는 금지 번호를 집합으로 만들어 포함 여부를 확인해요. sum(seen)은 bool에서 True가 1, False가 0으로 계산되는 성질을 이용해 방문 수를 더해요. n≤100이므로 제공된 재귀의 최대 호출 깊이도 100 이하예요.
입력 하네스의 input()은 한 줄의 문자열을 읽고, .split()은 공백으로 항목을 나눠요. map(int, ...)는 각 항목을 정수로 바꾸고 list(...)는 그 결과를 리스트로 모아요. range(n)은 0부터 n-1까지 반복해요. 하네스는 함수 호출을 위한 자체 연결이며 풀이의 반환 계약과 구분해요.