[BOJ][python] 24230_트리색칠하기

문제

예제 입력 :

# 예제 입력
7 # 트리를 구성하는 정점의 개수
0 0 2 0 1 2 2 # 1번 정점부터 7번 정점까지 각 색 정보
1 2
1 3
1 4
2 5
3 6
3 7

# 예제 출력
2

24230번: 트리 색칠하기

풀이 :

• key point :
  • 문제에서 “하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다” , “색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다” 는 말에 주목할 필요가 있다. 이 말은 즉 한 정점의 자식 정점은 자신의 정점이 덮어지기 전까지는 부모 정점과 똑같은 색으로 색칠되어 있다는 뜻이다.
    • 따라서 현재 정점과 현재 정점의 부모 정점의 색깔과 비교해서 다를 경우 +1 해주면 된다.
• Logic:
  • root 를 시작으로 bfs 를 순회하면서 현재 정점의 색깔과 부모 정점의 색깔이 다른 경우 +1 해준다.
  • root 가 처음에 하얀색이 아닌 경우 마지막에 +1 해줘야된다.

코드 :

# 83016KB / 1184ms

import sys
from queue import Queue
input = sys.stdin.readline

def tint_color(s,graph,stated):

    visited = [False for _ in range(V+1)]
    queue = Queue()
    queue.put(s)
    visited[s]=True
    count = 0

    while (queue.qsize()>0):
        v = queue.get()
        for w in graph[v]:
            if not visited[w]:
                visited[w]=True
                if stated[w-1] != stated[v-1]:
                    # stated[w-1] = stated[w-1]
                    count +=1
                queue.put(w)
    return count

V = int(input())      # 정점 수 
E = V - 1       # 간선 수 
stated_color_list = list(map(int,input().split()))  # 입력 받은 색깔 리스트 

tree = [[] for _ in range(V+1)] 
for _ in range(E):      # 그래프 생성
    v,w = map(int,input().split())
    tree[v].append(w)
    tree[w].append(v)

result = tint_color(1,tree,stated_color_list)

if  stated_color_list[0] != 0:  # root 가 흰색이 아니라면 1 증가
    result +=1

print(result)

---

느낀점 :

처음에 내가 생각한 로직 :

1. 따로 정점의 갯수만큼 하얀색(0) 으로 초기화 된 배열(A)를 만든다.
2. bfs를 Root(1) 부터 시작하며 현재 노드의 색깔이 정답 색깔과 다를 경우, 그 아래에 있는 모든 자식 노드의 색도 같이 바꿔 준다. 그리고 count(색칠횟수) 를 1 증가시킨다
3. 업데이트된 A 배열을 입력으로 받은 정답 배열과 같은지 검사한다.

문제점 :

매번 자식 노드의 색깔까지 고려하면서 배열(A)에 업데이트시키는 것은 엄청난 시간과 메모리 낭비가 든다,,

현재 탐색되는 노드가 되기까지 깊이가 깊은 그래프일수록 늦게 될텐데,, 매번 부모 는 물론이고 부모의 조상, 조상의 부모, 조상의 부모의 색깔이 바뀔때마다 똑같이 바꿔지므로 상당히 비효율적이라고 볼 수 있다.

결론적으로 이 문제의 해결책은 문제를 얼마나 잘 이해하느냐에 있었던 것 같다.

문제를 제대로 이해하는 것이 코드를 바로 짜는 것보다 훨씬 중요함을 깨달았다.

문제를 잘 이해하면 코드도 짧아지고 ! 정답에 가까워진다 !