[Python, 백준/21606번] 아침 산책

---

☑️ [Python, 백준/21606번] 아침 산책

1️⃣ 문제

문제 링크 : https://www.acmicpc.net/problem/21606

 

2️⃣ 접근

다른 정글 동료들에 비해서 이 문제를 늦게 접하게 된 편이었다. 문제의 난이도를 전해 들었어서 개인적으로 기대하고 있던 문제였는데, 조금 이전의 기억이라 정확하게 기억이 나지는 않지만, 5시간 정도를 투자해서 풀 수 있던 것 같다. 코치님들이 항상 어려운 문제는 30분을 고민하고 해답을 보고 다시 풀어보라고 말씀하셨었는데, 풀 수 있을 것 같은 느낌이 들어서 계속 붙잡고 있었다.

 

이 문제는 다른 블로그 포스팅과 AI를 보지 않고 풀어냈다는 점에서 기분이 좋았다.

 

처음에는 아래와 같이 접근했다.

# import sys
# from collections import deque
# sys.stdin = open('input.txt', 'r')
# sys.setrecursionlimit(10**6)

# def bfs() -> int:
#     q = deque()
#     answer = 0
    
#     for i in range(1, n_count + 1):
#         visit = [False] * (n_count + 1)
        
#         if n_type[i - 1] == '0':
#             continue

#         visit[i] = True
#         q.append(i)
        
#         while q:
#             curr_node = q.popleft()
#             visit[curr_node] = True
#             for adj_node in graph[curr_node]:
#                 if visit[adj_node] == False:
#                     if n_type[adj_node - 1] == '1':
#                         answer += 1
#                     else:
#                         q.append(adj_node)
#     return answer

# if __name__ == '__main__':
#     n_count = int(input())
#     n_type = input()

#     graph = [[] for _ in range(n_count+1)]

#     for _ in range(n_count - 1):
#         a, b = map(int, sys.stdin.readline().split())
#         graph[a].append(b)
#         graph[b].append(a)
    
#     print(bfs())

 

그래프를 만들어서 모든 Node를 순회하면서 인접 노드를 카운팅해줬다. 이렇게 작성하니까 점수가 60점이 나와서 문제를 조금 더 주의 깊게 살펴봤다.

 

Graph를 만들면서 어떻게 답을 구할 수 있을지 찾아봤는데, 실내 공간과 실내 공간이 이어지지 않은 Graph에 한해서 정답이 (실외노드와 인접한 실내 노드 수) x ((실외노드와 인접한 실내 노드 수) -1)임을 발견했고 실내 공간과 실내 공간은 처음 Grpah를 만들 때 +2를 더해줌으로서 처리할 수 있었다.

 

자세히 적고 싶은데, 기억나는게 이정도라서.. 확실히 알고리즘은 풀면서 생각을 정리하고 풀자마자 다시 한 번 정리하는게 중요하겠다.

 

3️⃣ 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)

def bfs() -> int:
    q = deque()
    indoor = 0
    sum = 0
    visit = [False] * (n_count + 1)
    
    # 전체 순회
    for i in range(1, n_count + 1):
        # 방문 여부 초기화 -> 새로운 노드가 돈다면
        # 실내일 경우 제외한다.
        if n_type[i - 1] == '1' or visit[i]:
            continue
        
        q.append(i)
        
        while q:
            cur_node = q.popleft()
            if n_type[cur_node - 1] == '0':
                visit[cur_node] = True
                
            # 인접 노드 확인
            for adj in graph[cur_node]:
                if visit[adj]:
                    continue
                
                if n_type[adj - 1] == '1':
                    sum += 1
                elif n_type[adj - 1] == '0':
                    q.append(adj)

        if sum <= 1:
            sum = 0
        indoor += sum * (sum - 1)
        sum = 0
    return indoor
                
if __name__ == '__main__':
    answer = 0
    n_count = int(input())
    n_type = input()

    graph = [ [] for _ in range(n_count+1)]

    for _ in range(n_count - 1):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
        
        if n_type[a - 1] == n_type[b - 1] == '1':
            answer += 2
    print(bfs() + answer)