소스코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input().strip()) # 정점 개수
A = [0] + list(map(int, input().strip()))
count = 0 # 가능한 서로 다른 산책 경로의 수
graph = [[] for _ in range(N + 1)]
for _ in range(N-1):
u,v = map(int, input().strip().split())
graph[u].append(v)
graph[v].append(u) # 무방향 그래프
# 경우 1 : 실내-실내 쌍인 경우
if A[u] == 1 and A[v] == 1:
count += 2
# 경우 2 : 실외 노드가 포함된 경우
visited = [False] * (N + 1)
def dfs(node):
indoor_count = 0 # 실외노드와 인접한 실내노드의 수
visited[node] = True # 방문처리
for neighbor in graph[node]:
# 실내 노드의 경우
if A[neighbor] == 1:
indoor_count += 1
elif not visited[neighbor] and A[neighbor] == 0:
# 실외노드인데 아직 방문 안 했다면
indoor_count += dfs(neighbor)
return indoor_count
# 결과 출력
for i in range(1, N+1):
if A[i] == 0 and not visited[i]:
indoor_count = dfs(i)
count += indoor_count * (indoor_count - 1)
print(count)
Python
복사
풀이
•
처음에는 실내로 시작해서 실외면 함수를 재귀호출하고, 실내 노드를 만나면 카운트를 증가시켜서 결과 처리 하는 형태로 제출했었습니다. 그렇게 할 경우, 방문 처리도 체크했다가 해제해야 다른 노드에서 해당 노드를 카운트할 수 있더라구요. 아 너무 복잡해진다 싶어서 다른 방법을 생각해봤습니다.
•
아예 (실내 - 실내) 경우와 (실외를 포함) 경우를 분리해서 고려해보면 좋겠다라고 판단했습니다. 실내끼리의 경우는 입력으로 주어지는 간선을 통해 확인하면 곧바로 결과에 반영할 수 있고, 실외가 포함된 경우만 잘 처리해주면 되겠다고 생각했습니다.
◦
실외 노드로 시작을 하는 함수입니다. 순회하면서 실외 노드를 만났을 때, 아직 방문하기 전이라면 DFS 함수를 시작합니다.
▪
방문처리를 합니다.
▪
DFS 함수에서는 인접한 실내 노드들의 개수를 구합니다. 인접 노드가 곧바로 실내라면 1을 증가합니다. 인접 노드가 실외라면 재귀 호출해서 해당 실외 노드의 인접한 실내 노드를 구해내고 이를 반영합니다.
◦
DFS 함수가 리턴한 실내 노드의 개수를 이용해 가능한 경우의 수를 구합니다(조합).
•
결과를 출력하면 끝!!
회고
•
처음에 간단하게 작성한 DFS 함수로 60점을 받은 후, 방향은 맞는 것 같은데 어딜 수정해야하지? 늪에 빠져서 허우적대다가 소모한 시간이 적지 않았습니다
. 질문을 자주 하는 것도 좋은 건 아니지만, 질문을 어느 타이밍때 해야 시간을 더 안 잡아먹고 다음으로 넘어갈 준비를 할 수 있을지 저만의 기준선을 잘 찾아봐야겠습니다.
. 질문을 자주 하는 것도 좋은 건 아니지만, 질문을 어느 타이밍때 해야 시간을 더 안 잡아먹고 다음으로 넘어갈 준비를 할 수 있을지 저만의 기준선을 잘 찾아봐야겠습니다.•
경우의 수를 분리해서 다루니 DFS 함수의 로직이 복잡하지가 않더라구요. 아무튼 한 함수에서 너무 많은 일을 하고 있다면 뭔가 잘못된건가 생각해볼 필요도 있겠습니다(물론 다른 방향이 맞는 지를 고민해볼 수 있는 능력을 키워야겠죠?).