[백준 2024/09/19] 21606번 아침 산책

1. 문제

https://www.acmicpc.net/problem/21606

 

2. 접근 방법

이번 문제는 고생을 너무 많이 했다.........................................진짜

처음에 접근 방법을 제대로 잡고 들어갔어야 했는데, 경우에 따라서 코드를 작성하다보니 너무 시간이 오래 걸렸다.

 

처음에는 각 vertex 별 검정 vertex 까지의 경우를 생각하면서 풀었다. 하지만, 5번 test case 에서 fail 하고 말았다.

즉, 다른 접근 방법이 필요로 했다.

 

몇 시간을 고민하다가 다른 동료 분의 도움을 받아서 풀 수 있었다. (압도적 감사)

 

 

이런 다양한 case 들이 있었다.

 

이제 본격적으로 문제 접근을 해보도록 하자

우선 for 문으로 각 vertex를 접근하였다.

 

1. 검정 vertex -> 흰색 : count x
2. 검정 vertex -> 검정 : count += 1

 

검정에서 흰색으로 가는 경우는 count 하지 않는다.

왜냐하면, 흰색 vertex에 for문으로 접근하는 경우에 count 해줄 것이기 때문이다.

검정에서 검정으로 접근하는 경우를 a -> b 라고 가정하자. b -> a 를 경우를 생각해서 + 2를 해줄 수 있지만, 포함하지 않는 이유는 추후에 for 문으로 b vertex 에 접근하게 될 경우에 b -> a가 count 될 것이기 때문이다.

 

나 같은 경우엔 v_list_location 이라는 dictionary를 선언하여, 특정 vertex에서 주변의 노드가 실내인지 실외인지 1, 0 으로 표현해 주었다.

 

이를 통해서, 검정 vertex(i) 에 접근하게 되었을 때, sum(v_list_location[i])를 통해서, 바로 주변 검정 노드의 개수를 count 할 수 있도록 하였다.

 

이제 for 문으로 흰색 vertex를 접근하게 되는 경우를 생각해 보자.

 

위 세 경우는 모두 동일한 가능한 경로 개수를 지니게 된다.

왜냐하면, 흰색 vertex의 경우엔, 건너가는 역할을 하지 start와 end 가 될 수 없기 때문이다.

 

또한, 4개의 vertex에서 2개를 고르고 * 2를 하게 되면 모든 경우를 포함하기 때문에, 4C2 * 2를 해주면 된다. (4P2와 동일)

 

따라서 흰색 vertex에 도달하게 될 경우엔, 

 

1. 흰색 vertex 주변에 검정 vertex 밖에 없다면 : (검정 vertex 개수) P2 를 paths_num 에 추가해 주면 된다.
2. 흰색 vertex 주변에 흰색 vertex가 있다면, 주변 흰색 vertex 에서의 검정 vertex의 개수를 count 해줌 -> 연결된, 흰색 vertex 주변의 total 검정 vertex 개수를 count 하고 combination 적용.

흰색 node 의 경우 중복적으로 접근하면 안되기 때문에, 접근했다면, Visited list를 이용해서 다시 접근하지 않도록 한다.

 

3. 코드

from collections import defaultdict
import math
import sys
sys.setrecursionlimit(10**6)

class Graph:
    def __init__(self, vertex, location):
        self.vertex = vertex
        self.location = [-1] + location
        self.v_list = defaultdict(list)
        self.v_list_location = defaultdict(list)
        self.paths = 0
        self.black_cnt = 0
        self.visited = [False] * (self.vertex + 1)

    def add_edges(self):
        u, v = map(int, input().split())
        self.v_list[u].append(v)
        self.v_list[v].append(u)
        self.v_list_location[u].append(self.location[v])
        self.v_list_location[v].append(self.location[u])


    def dfs(self, i):
        self.visited[i] = True
        for near_v in self.v_list[i]:
            if self.location[near_v]:
                self.black_cnt += 1
            elif not self.visited[near_v]:
                self.dfs(near_v)
    def get_path(self):
        for i in range(1, self.vertex+1, 1):
            if self.location[i]:
                self.paths += sum(self.v_list_location[i])
            elif not self.visited[i]:
                self.black_cnt = 0
                self.dfs(i)
                self.paths += math.comb(self.black_cnt, 2) * 2

        return self.paths



if __name__ == "__main__":
    vertex = int(input())
    location = list(map(int, input()))
    g = Graph(vertex, location)
    for i in range( vertex - 1 ):
        g.add_edges()
    print(g.get_path())