Krafton_jungle 5기 16일차 TIL - 알고리즘 문제풀이

1. 1916 최소비용 구하기

import math
import sys
import heapq
input = sys.stdin.readline


def make_graph(vertices, edges):
    # 빈 그래프 생성
    graph = [[] for _ in range(vertices+1)]
    for i in range(edges):
        # 그래프에 값 추가
        start_vertex, arrival_vertex, cost  = map(int, input().split())
        graph[start_vertex].append((cost, arrival_vertex))

    return graph


def dijkstra(graph, start_vertex):
    queue = []
    # 거리를 저장할 리스트 선언
    distances = [math.inf] * (vertices + 1)
    # 최초 시작 거리 = 0
    distances[start_vertex] = 0
    heapq.heappush(queue, (0, start_vertex))

    while queue:
        # 현재 정점과 비용
        cur_cost, cur_vertex = heapq.heappop(queue)
        # 이미 저장되어 있는 거리가 더 작으면
        if distances[cur_vertex] < cur_cost:
            continue
        # graph에 저장되어 있는 주변 노드 탐색
        for node in graph[cur_vertex]:
            # 주변 노드 + 자신의 값을 구하고
            cost = cur_cost + node[0]
            # 그 값이 이미 저장되어 있던 값보다 작으면
            if cost < distances[node[1]]:
                # 값을 변경해줌
                distances[node[1]] = cost
                # 그리고 변경된 값을 queue에 넣어서 탐색을 이어감
                heapq.heappush(queue, (cost, node[1]))
    return distances





# 정점의 수
vertices = int(input())
# 간선의 수
edges = int(input())

graph = make_graph(vertices, edges)

start_vertex, arrival_vertex = map(int, input().split())
print(dijkstra(graph, start_vertex)[arrival_vertex])

힙 정렬을 통해 다익스트라 알고리즘을 구현했다.

다익스트라 알고리즘에 익숙해지는데 가장 크게 도움을 준 문제.

 

2. 1916 최소비용 구하기

import math
import sys
import heapq
input = sys.stdin.readline


def make_graph(vertices, edges):
    # 빈 그래프 생성
    graph = [[] for _ in range(vertices+1)]
    for i in range(edges):
        # 그래프에 값 추가
        start_vertex, arrival_vertex, cost  = map(int, input().split())
        graph[start_vertex].append((cost, arrival_vertex))

    return graph


def dijkstra(graph, start_vertex):
    queue = []
    # 거리를 저장할 리스트 선언
    distances = [math.inf] * (vertices + 1)
    # 최초 시작 거리 = 0
    distances[start_vertex] = 0
    heapq.heappush(queue, (0, start_vertex))

    while queue:
        # 현재 정점과 비용
        cur_cost, cur_vertex = heapq.heappop(queue)
        # 이미 저장되어 있는 거리가 더 작으면
        if distances[cur_vertex] < cur_cost:
            continue
        # graph에 저장되어 있는 주변 노드 탐색
        for node in graph[cur_vertex]:
            # 주변 노드 + 자신의 값을 구하고
            cost = cur_cost + node[0]
            # 그 값이 이미 저장되어 있던 값보다 작으면
            if cost < distances[node[1]]:
                # 값을 변경해줌
                distances[node[1]] = cost
                # 그리고 변경된 값을 queue에 넣어서 탐색을 이어감
                heapq.heappush(queue, (cost, node[1]))
    return distances





# 정점의 수
vertices = int(input())
# 간선의 수
edges = int(input())

graph = make_graph(vertices, edges)

start_vertex, arrival_vertex = map(int, input().split())
print(dijkstra(graph, start_vertex)[arrival_vertex])

이것도 그냥 위 문제와 빼다박은 문제.

 

3. 2665 미로 만들기

import sys
import math
import heapq

input = sys.stdin.readline

direction_x = [1, -1, 0, 0]
direction_y = [0, 0, 1, -1]


def make_graph(n):
    graph = [[] for _ in range(n)]
    for i in range(n):
        row = input().rstrip()
        for j in row:
            graph[i].append(int(j))
    return graph


def dijkstar(cost = 0, y = 0, x = 0, visited = set()):
    # 값을 저장할 보드 추가
    check_cost_board = [[math.inf] * n for _ in range(n)]
    check_cost_board[0][0] = 0
    # 우선순위 큐 선언
    pq = []
    heapq.heappush(pq, (cost, y, x))
    while pq:
        cost, y, x = heapq.heappop(pq)
        visited.add((y,x))
        if y == n - 1 and x == n - 1:
            return cost
        for i in range(4):
            nx = x + direction_x[i]
            ny = y + direction_y[i]
            if (ny, nx) in visited:
                continue
            if 0 <= nx < n and 0 <= ny < n and check_cost_board[ny][nx] > cost + 1:
                if graph[ny][nx] == 0:
                    check_cost_board[ny][nx] = cost+1
                    heapq.heappush(pq, (check_cost_board[ny][nx], ny, nx))
                elif graph[ny][nx] == 1:
                    check_cost_board[ny][nx] = cost
                    heapq.heappush(pq, (check_cost_board[ny][nx], ny, nx))


n = int(input())
graph = make_graph(n)
print(dijkstar())

2차원 + 다익스트라 라고 생각하면 쉽다.

 

4. 14888 연산자 끼워넣기

import sys
import math
input = sys.stdin.readline

maximum = -math.inf
minimum = math.inf


def dfs(answer, cur = 0):
    global maximum, minimum
    if cur >= n-1:
        maximum = max (answer, maximum)
        minimum = min (answer, minimum)
        return
    for i in range(4):
        if operands[i] == 0:
            continue
        operands[i] -= 1

        if i == 0:
            dfs(answer + arr[cur + 1], cur + 1)
            operands[i] += 1
        if i == 1:
            dfs(answer - arr[cur + 1], cur + 1)
            operands[i] += 1
        if i == 2:
            dfs(answer * arr[cur + 1], cur + 1)
            operands[i] += 1
        if i == 3:
            dfs(int(answer / arr[cur + 1]), cur + 1)
            operands[i] += 1


# 입력받을 숫자의 갯수
n = int(input())
arr = list(map(int, input().split()))
operands = list(map(int, input().split()))

dfs(arr[0])
print(maximum)
print(minimum)

dfs 탐색으로 모든 경우의 수를 찾고, 해당 수들의 최대값, 최소값을 저장해서 풀었음

 

5. 21606 아침산책

해당 방법은 2가지 접근 방법으로 해결했다.

첫번째는 실내노드부터 실내 노드까지 모든 경로를 탐색하는 방법

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def make_graph(n):
    graph = [[] for _ in range(n+1)]
    for i in range(n-1):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    return graph


# 실내에서 부터 탐색 시작
def find_path(graph, start, res, visited):
    visited.add(start)
    for i in graph[start]:
        if i in visited:
            continue
        if plate[i] == 0:
            find_path(graph, i, res, visited)
        elif plate[i] == 1:
            res.add(i)
    return res


n = int(input())
a = input().rstrip()
plate = [0] * (n+1)
for i in range(1, len(a)+1):
    plate[i] = int(a[i-1])

graph = make_graph(n)

res = 0
visited = set()
for i in range(1, n+1):
    if i not in visited and plate[i] != 0:
        res += len(find_path(graph, i, set(), visited))

print(res)

해당 방법은 시간이 오래걸려서 108점이 나왔다.

 

그래서 생각해낸 방법이 실외 노드에서 인접한 실내 노드를 탐색하는 방법

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

result = 0

def make_graph(n):
    global result
    graph = [[] for _ in range(n+1)]
    for i in range(n-1):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
        if plate[v1] == 1 and plate[v2] == 1:
            result += 2
    return graph


# 실외에서 부터 탐색 시작
def find_path(graph, start, res, visited):
    visited.add(start)
    for i in graph[start]:
        if i in visited:
            continue
        if plate[i] == 0:
            find_path(graph, i, res, visited)
        elif plate[i] == 1:
            res.add(i)
    return res


n = int(input())
a = input().rstrip()
plate = [0] * (n+1)
for i in range(1, len(a)+1):
    plate[i] = int(a[i-1])

graph = make_graph(n)

visited = set()
for i in range(1, n+1):
    # 방문한 적 없고, 실외면
    if i not in visited and plate[i] != 1:
        path = (len(find_path(graph, i, set(), visited)))
        # 각 노드간의 연결 경로의 수는 path * (path - 1)
        result += path * (path - 1)

print(result)

해당 방법으로 풀이했다.

 

꼭 백준문제는 이렇게 조건 하나를 틀어서 내는 경우가 많더라

지금은 위상정렬을 응용한 문제를 풀고 있는데, 어떻게 코드로 구현해야 할 지 몰라서 다시 한번 개념을 잡고 가야할 것 같다.