연결된 장소를 한 번씩 방문하기

연결 관계를 이웃 리스트로 저장해요

2D 리스트·함수·재귀를 배웠어요. 장소를 0번부터 번호로 부르고, graph[node]에는 그 장소와 직접 연결된 이웃 번호를 담아요.

graph = [[1], [0, 2], [1], []]

0은 1과, 1은 0·2와, 2는 1과 연결돼요. 3은 연결이 없어요. 양방향 연결이므로 0의 이웃에 1을 넣으면 1의 이웃에도 0을 넣어요. 그림은 0에서 갈 수 있는 0·1·2와 분리된 3을 보여 줘요.

방문 표시를 먼저 남겨요

재귀로 이웃에 들어가더라도 이미 방문한 장소를 다시 방문하면 안 돼요. 0 → 1 다음에 1 → 0으로 돌아올 수 있기 때문이에요. visited[node]의 0은 아직 방문하지 않음, 1은 방문 완료예요.

def visit(node):
    visited[node] = 1
    total = 1
    for neighbor in graph[node]:
        if visited[neighbor] == 0:
            total = total + visit(neighbor)
    return total

node 자체를 먼저 1개로 세고, 아직 안 간 이웃의 방문 수를 더해요. graph와 visited는 프로그램에서 함께 쓰는 리스트예요. 함수가 visited의 칸을 바꾸면 다른 호출도 그 표시를 읽어요. 같은 장소를 두 번 세지 않아요. 이를 깊이 우선 탐색 DFS라고 해요.

분리된 장소와 시작 장소를 구분해요

같은 graph에서 visit(0)은 0·1·2를 세어 3을 반환해요. 3은 경로가 없어서 세지 않아요. visit(3)은 자기 자신만 세어 1이에요.

입력에서 이웃 리스트를 만들 때 각 장소마다 새 리스트를 만들어요. 한 장소를 먼저 방문 표시하므로 순환 연결과 중복 연결도 다시 세지 않아요. 과제는 0번 장소부터 시작하며 시작 장소도 결과에 포함해요.

직접 풀어봐요

양방향 연결을 읽고 0번 장소에서 갈 수 있는 서로 다른 장소 수를 출력해요. 시작 장소 0도 포함해요. 중복 연결과 자기 자신으로 가는 연결이 있어도 한 장소는 한 번만 세어요.

첫 줄 n(120), 둘째 줄 m(0100), 이후 연결마다 a 한 줄, b 한 줄이에요. 각 번호는 0~n −1이에요. 출력은 장소 수예요.

예시 1: n = 4, 연결[(0, 1),(1, 2)] → 3예요. 예시 2: n = 3, 연결[(1, 2)] → 1. 0은 분리돼 있어요.

4
2
0
1
1
2

3

3
1
1
2

1