[白俊]1606:朝の散歩
質問する
https://www.acmicpc.net/problem/21606
要害
キーは、現在のノードが室内か屋外かを知ることです.
この問題では,コア部分は
실내 - 실내であり,dfsを必要とせず,실내が실외に遭遇した場合,dfsの探索を行い,屋外に近い室内の個数を算出する.屋外に近い室内の個数を数えれば、室内の個数がnの場合、経路の個数はn * (n-1)である.室内−室内の場合は別とし,室内が室外に隣接する場合はdfsにより隣接室内の個数を計算し,最後に受信した全室内個数から経路の個数を計算する.
に答える
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(input()) # 정점의 수
place = [0] + list(map(int, list(input().strip()))) # 1은 실내, 0은 실외
node = [[] for _ in range(N+1)] # 노드
visited = [False] * (N+1) # 방문 기록
# 간선 정보 입력
for _ in range(N-1):
a, b = map(int, input().split())
node[a].append(b)
node[b].append(a)
# 실외와 인접한 실내의 개수 구하기
def dfs(i):
home_cnt = 0
for j in node[i]: # i의 인접노드 j
if place[j] == 1: # 실내일 때
home_cnt += 1
continue
else: # 실외일 때
if not visited[j]: # 실외에 방문한 적 없을 때
visited[j] = True
home_cnt += dfs(j)
return home_cnt
cnt = 0
# 인접 경로
for i in range(1, N+1):
if place[i] == 1: # 현재 노드가 실내일 때
for j in node[i]: # 인접노드
if place[j] == 1: # 실내일 때
cnt += 1
else: # 현재 노드가 실외일 때
if not visited[i]: # tmp로 방향이 switch된 것도 다 고려해주는 것! -> visited처리를 해줘야 중복 피할 수 있음
visited[i] = True
tmp = dfs(i)
cnt += tmp * (tmp-1)
print(cnt)Reference
この問題について([白俊]1606:朝の散歩), 我々は、より多くの情報をここで見つけました https://velog.io/@letsbebrave/백준-21606-아침-산책-4i69dxmlテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol