greentea31's Note

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

풀이 과정

이진 트리를 직렬화(일자로) 했다가 다시 역직렬화 하는 문제이다.

BFS로 트리를 순회하면서, 방문 순서대로 문자열에 넣었다. 방문한 노드가 실제 존재하지 않는 노드라면, 문자열에 #을 추가하게끔 하였다. 역직렬화 과정중 문자열에서 각 노드의 값을 다시 추출하기 편하도록 문자열에서의 노드들의 값은 공백으로 구분하게끔 했다.

예시와 같은 트리를 BFS로 방문하면서 앞서 언급한대로 직렬화 한다면 serial = "1 2 3 # # 4 5"가 직렬화된 문자열로 저장될 것이다.

역직렬화 과정때도 BFS 과정을 통해 다시 트리로 바뀌게끔 구현하였다. "1 2 3 # # 4 5" 라는 문자열이 다시 위의 그림과 같이 역직렬화 되도록 구현하였다. 말로 풀어 설명하는 것보다는 코드를 읽으면 이해가 갈 것이다.

소스 코드

class Codec:

    def serialize(self, root):
        serial = ""
        Q = deque([root])
        while Q:
            cur_node = Q.popleft()
            if not cur_node:
                continue
            serial += str(cur_node.val)
            serial += ' '
            if cur_node.val == '#':
                continue
            if cur_node.left:
                Q.append(cur_node.left)
            else:
                Q.append(TreeNode('#'))
            if cur_node.right:
                Q.append(cur_node.right)
            else:
                Q.append(TreeNode('#'))
        
        while serial and serial[-1] == '#':
            serial = serial[:-1]
        
        return serial
        

    def deserialize(self, data):
        index = 0
        data = data.split()
        length = len(data)
        if length == 0:
            return None
        if data[index] != '#':
            root = TreeNode(data[index])
            index += 1
        if index >= length:
            return root
        Q = collections.deque([root])
        
        while Q:
            cur_node = Q.popleft()
            if data[index] != '#':
                cur_node.left = TreeNode(data[index])
                Q.append(cur_node.left)
            index += 1
            if index >= length:
                return root
            if data[index] != '#':
                cur_node.right = TreeNode(data[index])
                Q.append(cur_node.right)
            index += 1
            if index >= length:
                return root
        
        return root

https://leetcode.com/problems/merge-two-binary-trees/

풀이 과정

두 개의 이진트리의 값을 더해서 합친 이진트리를 반환하는 문제이다.

재귀를 사용해 이진 트리의 모든 노드를 순회하면서 합쳐 새로운 이진 트리를 만들어 반환하게끔 하였다.

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 and root2:
            node = TreeNode(root1.val + root2.val)
            node.left = self.mergeTrees(root1.left, root2.left)
            node.right = self.mergeTrees(root1.right, root2.right)
            return node
        else:
            return root1 or root2

https://leetcode.com/problems/invert-binary-tree/

풀이 과정

모든 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 바꾸는 문제이다.

DFS 혹은 BFS로 트리의 노드들을 순회하면서, 왼쪽 자식노드와 오른쪽 자식노드를 변경해주면 된다.

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
        return None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        Q = collections.deque([root])
        while Q:
            node = Q.popleft()
            if node:
                node.left, node.right = node.right, node.left
                Q.append(node.left)
                Q.append(node.right)
        return root

https://leetcode.com/problems/longest-univalue-path/

풀이 과정

트리에서 같은 숫자로 이루어져 있는 가장 긴 경로를 구하는 문제이다.

DFS로 리프 노드에서부터 체크하면서 부모 노드의 값이 왼쪽 자식 노드의 값과 같으면 left 변수를 증가, 오른쪽 자식 노드의 값과 같으면 right 변수를 증가시키면서 정답을 구해주면 된다.

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    result = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            
            if node.left and node.left.val == node.val:
                left += 1
            else:
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else:
                right = 0
            
            self.result = max(self.result, left + right)
            return max(left, right)
            
            
        dfs(root)
        return self.result



https://leetcode.com/problems/diameter-of-binary-tree/

풀이 과정

이진 트리의 지름, 즉 이진 트리의 노드들 사이의 가장 긴 경로를 구하는 문제이다.

이진 트리의 지름은 루트 노드와 리프 노드 사이의 거리이거나, 리프 노드와 리프 노드 사이의 거리이다. 루프 노트와 리프 노드의 사이의 거리는 트리의 높이를 구하면 해결할 수 있는 문제이지만 리프 노드와 리프 노드 사이의 거리는 어떻게 문제를 해결할 것인가?

DFS로 각 노드들에 리프노드와의 거리를 상태값으로 부여하자. 그러면 특정 노드를 루트로 하는 트리의 Diameter는 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2가 된다.

이 모든 과정을 마쳤을 때, 루트 노드에 대해서 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2를 더해주면 전체 트리의 지름을 구할 수 있다. 

자식 노드가 없는 경우에는 그 자식 노드의 상태값을 -1로 가정하고 계산을 진행해주어야 트리의 지름을 정상적으로 구할 수 있다.

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    longest = 0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return -1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            self.longest = max(self.longest, left + right + 2)
            return max(left, right) + 1
        
        
        dfs(root)
        return self.longest

https://leetcode.com/problems/maximum-depth-of-binary-tree/

풀이 과정

이진 트리의 최대 깊이를 구하는 문제이다.

트리도 (사이클이 없는) 그래프이므로 BFS, DFS등으로 모두 순회할 수 있다. 깊이는 BFS로 트리를 순회해주면 구할 수 있다.

소스 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        Q = collections.deque([root])
        depth = 0
        
        while Q:
            depth += 1
            for _ in range(len(Q)):
                cur_root = Q.popleft()
                if cur_root.left:
                    Q.append(cur_root.left)
                if cur_root.right:
                    Q.append(cur_root.right)
        
        return depth

https://leetcode.com/problems/network-delay-time/

풀이 과정

노드와 간선이 주어질 때, 노드 k에서 시작해서 모든 노드를 순회하는데 걸리는 최소 시간을 구하는 문제이다. 순회가 불가능하면 -1을 출력해야 한다.

그래프에서 최소 거리, 최소 시간 문제를 풀 때는 BFS, 다익스트라, 플로이드, 벨만포드 알고리즘을 떠올릴 필요가 있고 이 문제에서는 간선의 가중치가 음수가 아님이 보장되므로 다익스트라를 통해서 문제를 해결하면 된다.

시작점 K와 나머지 모든 점의 최소 거리를 구하고, 거리의 최대값이 모든 점을 방문하는데 걸리는 시간이므로 이를 출력해주면 된다.

모든 정점으로의 거리가 추가되었는지 확인하고, 추가되지 않은 정점이 있으면 모든 정점을 순회하는게 불가능하다는 의미이므로 -1을 리턴해주면 된다.

소스 코드

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        dist = collections.defaultdict(int)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

https://leetcode.com/problems/course-schedule/

풀이 과정

어떤 지점을 방문하기 위해 방문해야 하는 선행 방문 지점이 주어질 때, 주어진 코스가 순회 가능한지 여부를 구하는 문제이다.

예를 들어 1을 방문하기 위해서 0을 방문해야 하고, 0을 방문하기 위해서 1을 방문해야 한다면, 두 지점 모두 방문이 불가능하므로 코스가 순회가 불가능하다고 할 수 있다.

문제에서 주어진 prerequisites를 그래프의 간선으로 생각해 그래프로 모델링 한 후, 그래프에서 사이클이 존재하면 코스가 순회 불가능, 사이클이 존재하지 않으면 코스가 순회가 가능하다고 판단해주면 된다.

visit set으로 방문점 파악, route set으로 사이클 존재 여부를 파악하게 하여 코드를 작성하였다. 방문점, 사이클 존재 파악시 in을 사용하면 시간복잡도가 O(N)이라 비효율적인 코드가 아닌가 하는 생각이 들 수 있다.

Python의 경우 list, tuple 자료형에서는 in 사용시 하나하나 순회하기 때문에 O(N)이지만, set이나 dictionary에서는 내부적으로 hash를 통해서 자료들을 저장하기 때문에 해시 충돌이 정말 많이 발생하지 않는 이상 O(1)로 작동한다.

소스 코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        route = set()
        visit = set()
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        
        def dfs(x):
            if x in route:
                return False
            if x in visit:
                return True
            
            visit.add(x)
            route.add(x)
            
            for arrive in graph[x]:
                if not dfs(arrive):
                    return False
            
            route.remove(x)
            return True
    
        for x in list(graph):
            if not dfs(x):
                return False

        return True

https://leetcode.com/problems/reconstruct-itinerary

풀이 과정

JFK에서 시작하는, 주어진 모든 비행 티켓을 사용하는 여행 경로를 구하는 문제이다. 경로는 여러가지가 존재할 수 있지만 사전식 순서로 앞선 경로만을 출력해야 한다.

비행기 티켓을 딕셔너리에 전부 넣어놓고, JFK에서 시작해 DFS 방식으로 사전식 순서가 앞선 도착지를 우선으로 탐방하여 문제를 해결하였다.

소스 코드

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        answer = []
        for depart, arrive in sorted(tickets, reverse=True):
            graph[depart].append(arrive)
        
        def dfs(x):
            while graph[x]:
                dfs(graph[x].pop())
            answer.append(x)
        
        dfs('JFK')
        return answer[::-1]

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

풀이 과정

친분 관계 사이를 기반으로 튜터-튜티 지정이 가능하며, 교육 자료는 튜터 -> 튜티 방향으로 전달할 수 있다. 교육생간의 친분 관계가 포레스트인 그래프로 주어질 때 모든 교육생에게 자료가 전달되기 위해 찬솔이가 전해줘야 하는 인원수의 최소가 될 때의 튜터-튜티 관계를 정하는 경우의 수를 구하는 문제이다.

각 연결요소에 속해있는 정점의 개수를 정답 변수에 곱하는 방법으로 답을 구할 수 있다. 1 - 2 - 3, 4 - 5 - 6 - 7 - 8 이렇게 연결되어 있을 때의 경우는 3x5 = 15개의 경우의 수가 나올 것이다.

소스 코드

import sys
import collections


def bfs(x, visit, graph):
    q = collections.deque([x])
    visit[x] = True
    number = 1

    while q:
        cur = q.popleft()
        for nxt in graph[cur]:
            if visit[nxt]:
                continue
            q.append(nxt)
            visit[nxt] = True
            number += 1

    return number


graph = collections.defaultdict(list)
N, M = map(int, sys.stdin.readline().split())
visit = [False for _ in range(N+1)]
answer = 1
mod = 1000000007

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for v in range(1, N+1):
    if not visit[v]:
        answer *= bfs(v, visit, graph)
        answer %= mod

print(answer)