[백준 17501번] 수식 트리

난이도: 골드 1

문제 링크: www.acmicpc.net/problem/17501

17501번: 수식 트리

문제 17501번: 수식 트리

제겐 아직 너무나도 생소한 bfs를 이용하는 문제입니다.

DFS는 그래도 문제 한 두 개 풀어봐서 기억이라도 하는데, BFS는 자료구조 책에서만 접해봐서 너무 생소했어요.

 

접근 방법을 열거하자면...

• 시작에 앞서, tree_node 구조체를 만든다. 이 구조체는 연산자, 왼쪽 자식 노드, 오른쪽 자식 노드, count 변수를 멤버로 가진다.
• 전역 array num, sub, node를 만든다. num, sub는 int형이며, node는 tree_node형이다.
• BFS 연산에 이용하기 위한 queue q를 만든다. 이 queue는 tree_node형이다.
• 입력을 받는다.
  • 피연산자 노드는 num 배열에 입력한다. 계산의 편의성을 위해, index는 1부터 N까지로 한다 (일부러 문제의 조건에 맞춤).
  • 연산자 노드는 node 배열에 입력한다. 계산의 편의성을 위해, index는 N부터 2N-1까지로 한다
• 맨 마지막 연산자 node를 q에 enque한 후, bfs를 수행한다.
• bfs는 queue가 빌 때까지, 다음 동작을 수행한다:
  • tree_node형 변수 front를 선언하고, q.front()의 값을 담는다. 이후 q.pop()을 수행.
  • 좌 node에 대해, 다음을 수행한다:
    
    • 왼쪽 자식 node의 값이 N보다 작거나 같으면, sub [왼쪽 자식 노드] = front.count를 담는다.
    • 그렇지 않으면, q에 node[front.left]의 {sym, left, right, count + front.count}를 멤버로 가지도록 push 한다.
  • 우 node에 대해, 다음을 수행한다:
    • 오른쪽 자식 node의 값이 N보다 작거나 같으면, sub [오른쪽 자식 노드] = front.count + (front.sym=='-')을 담는다.
    • 그렇지 않으면, q에 node [front.right]의 {sym, left, right, count + front.count + (front.sym=='-')}을 멤버로 가지도록 push 한다.
  • 위 bfs가 가지는 의미는 다음과 같다:
    • 1~N번 node는 피연산자, N+1 ~ 2N-1번 노드는 연산자이다.
    • 자식 node의 값이 N보다 크다는 말은 자식node 역시 연산자임을 의미한다. 이 경우, q에 자식 node의 정보를 push 한다.
    • 자식 node의 값이 N보다 작거나 같을 경우, 자식 node는 피연산자이다. 이 경우, sub배열에 node번호를 index로 하여, 현재 node의 count값을 담는다.
    • 오른쪽 자식 node의 경우, 현재 node가 연산자 node이며 '-'를 나타낼 경우, count값에 1을 추가로 더한다.
• bfs가 완료되면, sub배열에는 각 node번호를 index로 하여, 값이 들어있다.
• for문을 이용하여, sub배열에 담긴 각 node번호의 count 누적 값이 홀수인 횟수를 센다.
• sort를 이용하여 입력된 피연산자가 담긴 배열 num을 오름차순으로 정렬한다.
• 작은 값 들일수록 빼고, 큰 값들일수록 더하면 그 결과가 최대가 된다.
  • 따라서 앞에 홀수를 센 횟수만큼, num에서 값을 꺼내어 answer에 뺀다.
  • 나머지 횟수 동안, num에서 값을 꺼내어 answer에 더한다.
• answer를 출력한다.

인터넷에서 글과 코드를 참고하여 답을 작성하였는데,

블로그에 글을 작성하고 있는 지금도 코드 내용이 100% 이해가 되지 않아서 안타깝네요.

그럼에도 bfs에 대해, 또 트리를 활용하는 문제에 대한 좋은 경험이 된 것 같아 만족스럽습니다.

 

참고한 글은 아래와 같습니다:

• gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
• home-body.tistory.com/648

이번 문제는 특히 검색한 자료와 코드를 많이 참고해서, 온전히 제 힘으로 푼 문제라고 보기는 어렵습니다.

BFS에 익숙해지고자... 다른 분들 코드를 따라가며 배웠다고 생각해요.

 

*코딩 스터디 그룹을 통해 접한 문제입니다 (7주차 4번 문제). 링크

CodeTest-StudyGroup/Code-Test-Study