[아침 산책]
# 문제
아침 산책을 즐기는 서현이는 서울과학고에 입학해서도 아침 산책을 즐기려고 합니다. 서현이는 산책을 위해 서울과학고의 지리를 분석했고, 그 결과 서울과학고를
$N$개의 장소를
$N-1$개의 길이 잇는 트리 형태로 단순화시킬 수 있었습니다. 트리 구조이므로, 모든 장소를 몇 개의 길을 통해 오고갈 수 있습니다.
아침 산책은 시작점과 도착점을 정하고, 시작점에서 도착점까지 트리 위의 단순 경로(같은 점을 여러 번 지나지 않는 경로)를 따라 걷게 됩니다. 트리 위의 두 점 사이의 경로는 유일하므로 시작점과 도착점이 정해지면 경로는 유일하게 결정됩니다.
$N$개 장소 중에 일부 장소는 실내이며, 나머지 장소는 실외입니다. 서현이는 산책을 시작하기 전부터 운동을 하는 것을 원치 않기 때문에, 산책의 시작점과 끝점은 모두 실내여야 합니다. 또한, 산책 도중에 실내 장소를 만나면 산책을 그만두고자 하는 욕구가 생기기 때문에, 산책 경로 위에 시작점과 끝점을 제외하고 실내 장소가 있으면 안 됩니다.
서현이는 매일 다른 산책 경로를 걷고자 합니다. 서로 다른 산책 경로가 몇 가지 있는지 구해 봅시다.
# 입력
첫 줄에는 정점의 수 $N$이 주어집니다.
둘째 줄에는 1과 0으로 이루어진 길이 $N$의 문자열 $A$가 주어집니다. $i$번째 문자 $A_i$가 1일 경우 $i$번 장소는 실내이며, 0인 경우 $i$번 장소는 실외입니다.
셋째 줄부터 $N+1$번 줄까지는 $i+2$번 줄에 트리의 각 간선을 나타내는 두 정수 $u_i$, $v_i$가 주어집니다. 이는 $i$번째 간선이 $u_i$번 정점과 $v_i$번 정점을 연결한다는 의미입니다.
# 출력
가능한 서로 다른 산책 경로의 수를 출력합니다.문제의 조건은 아주 간단하다. 실내에서 출발하고, 실내에서 끝나는 경로를 구하면 된다.
중간에 거쳐가는 실외가 몇개인지는 신경쓰지 않아도 된다. (심지어 실외가 0개인 경로도 가능하다!)
실외를 거치는 경우와 실외를 거치지 않는 경우를 각각 알아보자!
실외를 거치는 경우
1. 실외가 하나인 경우
실내인 정점 하나를 시작점으로 잡고, 나머지 실내인 정점 중에서 하나에 도착하면 경로가 끝난다.
시작하는 정점과 그 정점을 제외한 정점을 가는 경우를 구하면 되므로
실내의 개수를 N이라고 했을 때, N * (N-1)로 구할 수 있다.
👉 DFS 함수에서 인접한 실내 정점의 개수를 세어서 리턴해준다.
def DFS(start):
visited[start] = True # 방문 처리
inside_count = 0 # 현재 노드와 인접한 실내 노드 개수를 저장할 변수
for v in graph[start]:
# 인접한 노드가 실내라면
if inside[v] == '1':
inside_count += 1 # 실내 노드 개수 증가
return inside_count # 실내 노드 개수 반환2. 실외가 두 개 이상인 경우
실외가 이어져있다면, 여러개여도 완전 똑같다.
실외를 몇개를 거치는 지는 상관 없기 때문!
실외 노드의 인접 노드를 탐색하다가 실외 노드를 만나게 된다면
그 노드를 타고 가서 그 실외 노드와 인접한 실내 개수를 세어와서 더해주면 된다.
👉 DFS 함수의 for 문 안에서 실외인 경우 추가
# 인접한 노드가 실외라면
elif not visited[v] and inside[i] == "0": # 그 노드에서부터 탐색하여 실내 노드 개수 증가
inside_count += DFS(v)🤔 실외가 이어져있지 않다면?! 👇
3. 실외가 떨어져 있는 경우
실외가 떨어져 있다면,
각 실외와 인접한 실내들만 생각해서 각각 경로를 구하면 된다.
실내 2를 기점으로 각 실외와 인접해있는 실내가 나눠지므로
실내 2를 기점으로 쪼개버린당
이렇게 쪼개진 그래프에서 이전과 마찬가지로 각각 경로를 구하고 더해주면 된다.
왼쪽에서는 3 * (3 - 1) = 6
오른쪽에서는 2 * (2 - 1) = 2
이 둘을 더해서 총 8개의 경로가 나온다.
즉, 실외를 거치는 경우 1 ~ 3 모든 경우에서 동일하게
실외를 기점으로 실외와 인접한 실내 노드의 개수 N만 구해서 N * (N-1)로 경로의 수를 찾으면 된다.
👇 위의 1,2 코드를 합치고, DFS 함수에서 리턴 받은 실내 노드의 개수로 총 경로 개수를 계산하는 코드
def DFS(start):
visited[start] = True # 방문 처리
inside_count = 0 # 현재 노드와 인접한 실내 노드 개수를 저장할 변수
for v in graph[start]:
# 인접한 노드가 실내라면
if inside[v] == '1':
inside_count += 1 # 실내 노드 개수 증가
# 인접한 노드가 실외라면
elif not visited[v] and inside[i] == "0": # 그 노드에서부터 탐색하여 실내 노드 개수 증가
inside_count += DFS(v)
return inside_count # 실내 노드 개수 반환
for i in range(1, N+1):
if inside[i] == '0' and not visited[i]: # 시작이 실외일 때만 탐색
result = DFS(i) # DFS를 통해 인접한 실내 노드 개수를 계산
total += (result) * (result - 1) # 경로의 개수 추가실외를 거치지 않는 경우
실외를 거치지 않는다는 것은
실내에서 바로 실내로 이동하는 것이고
실내를 만나게 되면 경로가 종료되므로
실내에 인접한 정점이 실내일 경우만 해당된다.
그리고 실내1 -> 실내2와 실내2 -> 실내1을 별개로 구분하므로 각각 세어줘야 한다.
이 경우는 간선 정보를 입력받을 때
두 정점이 모두 실내인 경우, 총 경로 수에 2를 더해주기만 하면 된다.
for _ in range(N-1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
# 두 정점 모두 실내이면 경로의 수 2 증가
if inside[a] == "1" and inside[b] == "1":
total += 2끝!🥰
전체 코드
import sys
sys.setrecursionlimit(10**6)
N = int(input())
inside = '0' + input() # 각 노드가 실내(1)인지 실외(0)인지 저장한 문자열
# 노드 번호를 index로 접근하기 위해 앞에 0 추가
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
total = 0 # 경로의 개수를 저장할 변수
for _ in range(N-1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
# 두 정점 모두 실내이면 경로의 수 2 증가
if inside[a] == "1" and inside[b] == "1":
total += 2
def DFS(start):
visited[start] = True # 방문 처리
inside_count = 0 # 현재 노드와 인접한 실내 노드 개수를 저장할 변수
for v in graph[start]:
# 인접한 노드가 실내라면
if inside[v] == '1':
inside_count += 1 # 실내 노드 개수 증가
# 인접한 노드가 실외라면
elif not visited[v] and inside[i] == "0": # 그 노드에서부터 탐색하여 실내 노드 개수 증가
inside_count += DFS(v)
return inside_count # 실내 노드 개수 반환
for i in range(1, N+1):
if inside[i] == '0' and not visited[i]: # 시작이 실외일 때만 탐색
result = DFS(i) # DFS를 통해 인접한 실내 노드 개수를 계산
total += (result) * (result - 1) # 경로의 개수 추가
print(total)