[알고리즘] - 코딩 테스트 공부 (2022 카카오 테크 인턴십)

• 이번 문제는 코딩 테스트 공부 입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

• 넓이 우선 탐색(BFS)을 활용하여 문제에 접근했습니다.
• (알고력, 코딩력)을 하나의 위치 값으로 보고, (목표 알고력, 목표 코딩력)으로 가는 최소 비용(시간)을 구하는 방식으로 접근했습니다.
• 목표 알고력과 목표 코딩력은 해결해야 하는 문제들의 alp_req, cop_req 중 각각 가장 큰 값으로 설정했습니다. 그렇게 해야 모든 문제를 해결할 수 있기 때문입니다.
• 이후 BFS를 활용해서 (초기 알고력, 초기 코딩력)에서 출발하여 (목표 알고력, 목표 코딩력)으로 가는 최소 비용을 탐색했습니다.

주의 사항

• 이 때, 탐색하는 과정에서 정확히 목표 알고력 혹은 목표 코딩력에 도달하지 않는 경우가 존재합니다. 예를 들어 현재의 코딩력이 3이고 목표 코딩력이 5일 때, 어떤 문제를 풀어 코딩력 3을 높이면 목표 코딩력 5를 초과하는 값을 가지게 됩니다.
• BFS 탐색을 위해 선언한 그래프의 범위가 (목표 알고력, 목표 코딩력)까지만 커버하고 있음으로, 이에 대한 처리가 필요합니다.
• 생각해보면 목표를 넘어가는 경우에도 결국 문제를 해결할 수 있는 상황임으로, 문제 명세상 정확히 목표에 도달하는 경우와 다르지 않다는 것을 알 수 있습니다. 그렇기에 목표 값을 초과하는 경우를 목표 값에 정확히 도달하는 경우로 수정해줌으로써 최종적으로 (목표 알고력, 목표 코딩력)을 넘어서는 것들 중 최단 시간을 구할 수 있도록 구현했습니다.

구현

• BFS 탐색 과정에서 간선의 역할은 문제에서 명세된 알고력과 코딩력을 높이는 방법이 대신합니다.
• 즉, 공부를 통해 알고력, 코딩력을 증가시키는 경우 와 문제 해결을 통해 증가시키는 경우 를 해당 위치에서 다른 위치로 가게 만들어 주는 일종의 간선처럼 생각하면 됩니다.
• 최종 구현 내역은 아래와 같습니다.

# Programmers 118668, 코딩 테스트 공부
from collections import deque
INF = int(1e9)

def solution(alp, cop, problems):
    # 1. 목표치 설정
    t_alp, t_cop = 0, 0
    for problem in problems:
        al, co = problem[0], problem[1]
        if t_alp < al:
            t_alp = al

        if t_cop < co:
            t_cop = co

    # visit의 각 값은 해당 위치로 가는 최소 시간을 의미
    visited = [[INF] * (t_cop + 1) for _ in range(t_alp + 1)]

    # al,co가 처음부터 t_alp와 t_cop보다 크다면 최대값으로 줄임(인덱스 에러 방지)
    if alp > t_alp:
        alp = t_alp

    if cop > t_cop:
        cop = t_cop

    # 2. bfs 탐색
    bfs(problems, (alp, cop), visited, t_alp, t_cop)

    # 3. 목표 위치의 최솟값 출력
    answer = visited[t_alp][t_cop]

    return answer

def bfs(graph, cur_node, visit, t_alp, t_cop):
    # 시작 노드는 0으로 업데이트 업데이트
    al, co = cur_node
    visit[al][co] = 0

    queue = deque([cur_node])

    while queue:
        tg_a, tg_c = queue.popleft()

        # 문제를 풀어서 실력을 늘리는 방식
        for node in graph:
            a_req, c_req, a_rw, c_rw, cost = node
            # 해당 문제를 풀 수 있는 것이라면
            if tg_a >= a_req and tg_c >= c_req:
                # 움직일 위치 업데이트
                mv_a, mv_c = tg_a + a_rw, tg_c + c_rw

                # 만약 mv_a나 mv_c가 범위를 벗어난다면 범위 최대값으로 맞춰줌
                # 범위가 벗어나는 것도 목표 달성임으로 '목표 위치'로 값을 갱신
                if mv_a > t_alp:
                    mv_a = t_alp

                if mv_c > t_cop:
                    mv_c = t_cop

                # 갈 수 있는 위치의 기존 cost 값보다 줄일 수 있다면 방문
                if visit[mv_a][mv_c] > visit[tg_a][tg_c] + cost:
                    visit[mv_a][mv_c] = visit[tg_a][tg_c] + cost
                    # queue에 옮길 위치를 넣어줌
                    queue.append((mv_a, mv_c))

        # 공부해서 실력을 늘리는 방식
        # 1) 알고리즘 공부
        mv_a, mv_c = tg_a + 1, tg_c
        if mv_a > t_alp:  # 범위 벗어나지 않게 조정
            mv_a = t_alp

        if visit[mv_a][mv_c] > visit[tg_a][tg_c] + 1:
            visit[mv_a][mv_c] = visit[tg_a][tg_c] + 1
            # queue에 옮길 위치를 넣어줌
            queue.append((mv_a, mv_c))

        # 2) 코딩 공부
        mv_a, mv_c = tg_a, tg_c + 1
        if mv_c > t_cop:  # 범위 벗어나지 않게 조정
            mv_c = t_cop

        if visit[mv_a][mv_c] > visit[tg_a][tg_c] + 1:
            visit[mv_a][mv_c] = visit[tg_a][tg_c] + 1
            # queue에 옮길 위치를 넣어줌
            queue.append((mv_a, mv_c))

Lesson

• (알고력, 코딩력)을 일종의 위치로 생각하는 아이디어를 떠올리기까지 시간이 걸렸지만 아이디어를 떠올린 이후에는 생각보다 간단하게 BFS를 적용할 수 있었던 것 같습니다. 그래프 탐색 문제를 다양하게 풀어보며 감을 익혀야 할 것 같습니다.