3월 1주차 코딩 테스트

목차

1. 방탈출 열쇠편
2. 좀비 바이러스 성역
3. 평면 상의 MST
4. 거꾸로 BFS
5. 점프!

1. 방탈출 열쇠편

풀이

def solution(maze):
    def subprob(a, b, start):
        m = b[0] - a[0] + 1
        n = b[1] - a[1] + 1
        dp = [[0]*n for _ in range(m)]

        for i in range(m):
            if maze[a[0]+i][a[1]] == 1:
                break
            dp[i][0] = start
        
        for j in range(n):
            if maze[a[0]][a[1]+j] == 1:
                break
            dp[0][j] = start
        
        for i in range(1, m):
            for j in range(1, n):
                if maze[a[0]+i][a[1]+j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1] % 1007
    
    M, N = len(maze), len(maze[0])

    key = None
    for i in range(M):
        for j in range(N):
            if maze[i][j] == 2:
                key = (i, j)
                break
        if key:
            break
    
    sub_sol = subprob((0, 0), key, 1)
    if sub_sol == 0:
        return 0
        
    return subprob(key, (M-1, N-1), sub_sol)

Test case

# 테스트 1
입력값 〉 [[0, 1, 0], [0, 2, 0], [1, 0, 0]]
기댓값 〉 2

# 테스트 2
입력값 〉 [[0, 1, 0, 0], [1, 2, 0, 0], [1, 0, 0, 0]]
기댓값 〉 0

2. 좀비 바이러스 성역

풀이

def solution(N, graph, infected):
    parent = list(range(N))
    rank = [1 for _ in range(N)]
    
    def find(node):
        if parent[node] == node:
            return node
        
        parent[node] = find(parent[node])
        return parent[node]
    
    def union(p, q): 
        prt, qrt = find(p), find(q)
        if prt == qrt:
            return False 
        if rank[prt] > rank[qrt]:
            prt, qrt = qrt, prt
        parent[prt] = qrt
        rank[qrt] += rank[prt]
        return True 
    
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                union(i, j)
    
    infected.sort()

    comps = {}
    for i in infected:
        if find(i) in comps:
            comps[find(i)].append(i)
        else:
            comps[find(i)] = [i]
    
    max_ind = -1
    max_size = -1
    for i in infected:
        current_size = rank[find(i)]

        if len(comps[find(i)]) > 1:
            current_size = 0
        if current_size > max_size:
            max_ind = i
            max_size = current_size

    return max_ind

Test case

# 테스트 1
입력값 〉 3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]], [0, 2]
기댓값 〉 0

3. 평면 상의 MST

풀이

from heapq import heappush, heappop

def solution(x, y):
    n = len(x)
    root = list(range(n))
    rank = [1]*n

    def union(i, j):
        i_root = find(i)
        j_root = find(j)
        if i_root != j_root:
            if rank[i_root] >= rank[j_root]:
                root[j_root] = i_root
                rank[i_root] += rank[j_root]
            else:
                root[i_root] = j_root
                rank[j_root] += rank[i_root]
        
    def find(i):
        if i != root[i]:
            i = find(root[i])
        return root[i]
    
    def manhattan(i, j):
        return abs(x[i] - x[j]) + abs(y[i] - y[j])
        
    heap = []
    for i in range(n-1):
        for j in range(i+1, n):
            d = manhattan(i, j)
            heappush(heap, (d, i, j))
    
    total_dist = 0
    edges = []
    while len(edges) < n - 1:
        d, i, j = heappop(heap)
        if find(i) == find(j):
            continue
        union(i, j)
        edges.append((d, i, j))
        total_dist += d
    
    return total_dist

Test case

# 테스트 1
입력값 〉 [0, 0, 3, 3, 6], [0, 3, 1, 4, 3]
기댓값 〉 14

4. 거꾸로 BFS

풀이

def solution(N, left, right):
    adj_list = [[None, None] for _ in range(N)]

    for p, c in left:
        adj_list[p][0] = c
    
    for p, c in right:
        adj_list[p][1] = c
    
    is_visited = [False for _ in range(N)]
    answer = []

    def dfs(node):
        left, right = adj_list[node]

        if (not left or is_visited[left]) and \
         (not right or is_visited[right]):
            answer.append(node)
            is_visited[node] = True
            return

        if right and not is_visited[right]:
            dfs(right)

        if left and not is_visited[left]:
            dfs(left)
        
    while not all(is_visited):
        dfs(0)
    
    return answer

Test case

# 테스트 1
입력값 〉 6, [[0, 1], [1, 5], [2, 3]], [[0, 2], [3, 4]]
기댓값 〉 [4, 5, 3, 1, 2, 0]

5. 점프!

풀이

def solution(nums):
    max_reach = 0
    n = len(nums)
    
    for i in range(n):
        if i > max_reach: 
            return False
        max_reach = max(max_reach, i + nums[i]) 
        if max_reach >= n - 1: 
            return True

    return False

Test case

# 테스트 1
입력값 〉 [3, 4, 1, 1, 0, 3]
기댓값 〉 true

# 테스트 2
입력값 〉 [2, 3, 5, 2, 0, 2, 1, 1, 0, 0, 4]
기댓값 〉 false

출처

해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.

모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.