23.03.31 파이썬 코딩 퀴즈#207 모두 0으로 만들기(프로그래머스 스쿨)

이번 문제는 모두 0으로 만들기 문제이다.

문제를 잘 이해해야 하며, 문제 설명을 이해하지 못하면 풀이가 불가능한 문제이다.

먼저 전달받은 배열은 각 점에 가중치가 부여된 트리이다.

사용 가능한 연산은 연결된 두 점을 골라서 한쪽은 1 증가, 다른 한쪽은 1 감소이다.

제한 사항을 보면서 문제를 다시 확인해보자. (사실 제한사항이 아니라 문제 설명에 가깝다)

a 는 각 정점의 가중치를 의미한다.

edges 는 각 정점이 연결된 번호를 나타낸다.

입출력 예 1을 그림으로 나타내면 위와 같다. 즉 0,1,2,3,4 5개의 정점이 존재하고, 각 정점의 가중치는 a[i] 와 같다.

그리고 연결된 정보 edges 를 토대로 그림을 그리위 위 그림의 형태로 나온다.

 

입출력 예 2를 그림으로 그리면 위와 같다. 눈으로 알 수 있듯이 전부 0으로 만드는것이 불가능하다.

 

이제 다시 문제로 돌아와서 모든 값을 0으로 만들 수 있는 방법에 대해서 생각을 해보자.

위 그림처럼 a = [5, -3, -2] 라고 전달받아 트리를 그려 보았다.

-3을 중심으로 연결되었다고 보면, (-3,-2) 를 선택하여 (-5,0)을 만들고 (2회)

그 다음 다시 (5,-5)를 선택하여 0을 만들어 주면 된다 (5회). 총 7회

반대로 실행해도 결과는 같다

하지만 -3 이 아닌 5를 중심으로 두 정점이 연결되어 있다면 결과가 달라진다.

(5,-3)을 이용해서 (2,0)을 만들고(3회), 다시 (2,-2)를 선택해서 (0,0)을 만들어 주면 된다 (2회). 총 5회 

역시 반대로 실행해도 결과는 같다

마지막으로 -2가 중심이라면 

(-3,-2)를 선택하여 (0,-5)를 만든 다음(3회), (5,-5)를 선택하여 (0,0)을 만들어야 한다(5회) 총 8회

역시 반대도 마찬가지이다.

 

위 3가지 경우에서 알 수 있듯이 연결된 정점들의 기준점에 의해 연산횟수가 달라진다.

즉 각 정점이 연결되어 있을때, 정점이 합치는 지점을 중심으로 연산이 이루어지며, 이때 연결된 정점의 절대값의 합이다.

즉 모두 0으로 만들 수 있는 경우, 반드시 연결이 한개만 존재하는 지점(가장 하위)에서 시작해서 역으로 계산하며 올라와야 한다. 연산을 하는것이 아닌 아래쪽에서 부터 값을 합산하며 올라와 최종 값이 0 이 되는 최소 지점을 찾으면 된다.

 

이제 모두 0으로 만들기가 불가능한 경우를 살펴보자.

입출력 예 2에서 알 수 있듯이 a의 합이 0이 아닌 경우라면 모두 0으로 만들 수 없다.

그 이유는 연산 규칙에 의해 하나의 값이 1 증가 되면 하나의 값은 -1 감소되기 때문이다.

 

그렇게 첫번째 코드를 작성하였다.

먼저 graph를 만들어 각 정점의 연결 정보를 저장하고 이를 토대로 0번 정점부터 탐색을 시작했다.

탐색의 시작점은 어디가 되든 의미가 없다. 왜냐하면 해당 정점을 기준으로 계속해서 파고들어 가기 때문이다.

한가지 짜면서 머리가 아팠던 부분은 바로 answer에 어떤 값을 추가할 것인지였다.

입출력 예 1 그림을 살펴보면

0 에서 시작한 dfs() 함수는 3번을 호출하고, 다시 3번의 dfs() 는 2번과 4번을 호출한다.

이때 2번과 4번은 아무값이 없기 때문에(이미 3번은 방문처리가 됨) 그대로 answer 에 2와 2를 추가해주게 된다.

그리고 3번 그리고 그 값을 다시 3번에 추가해 준다. 그리고 다시 3번은 5를 가지게 된다. 다시 3번의 dfs()는 answer에 5를 추가해주고 0번의dfs()로 다시 돌아온다. 그렇게 되면 a의 값은 0이 되며, 최종적으로 answer은 9가 된다.

이 개념이 사실 아직도 생소한다. 거의 억지로 짜맞춘 느낌으로 코드를 작성했다.

 

그런데 거의 모든 문제에서 시간초과에 걸렸다.... 

그리고 1분만에 수정해서 통과했다.... 아 왜 자꾸 방문처리 리스트를 빈 리스트로 만드는지... 내 자신이 한심하다.

설명을 읽고 문제의 개념만 파악한다면 그렇게 어렵지 않은 문제이다.