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

1. 11725 트리의 부모찾기

import sys
from collections import deque
input = sys.stdin.readline

result = []


def bfs(visited, result):
    queue = deque([1])
    visited.add(1)
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                result[neighbor] = vertex
                visited.add(neighbor)
    return result


n = int(input())
graph = [[] for _ in range(n + 1)]

for i in range(n-1):
    vertex, edge = map(int,input().split())
    graph[vertex].append(edge)
    graph[edge].append(vertex)

result = [0] * (n+1)

result = bfs(set(), result)
for i in range(2, len(result)):
    print(result[i])

bfs를 통해 해당 노드의 부모를 배열에 저장하는 방법을 사용했다.

 

 

2. 1707 이분그래프

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

n = int(input())

def make_graph(vertex, edges):
    # 총 정점과 총 간선의 개수
    # 그래프 생성
    graph = [[] for _ in range(vertex + 1)]
    # 간선 정보 입력
    for edge in range(edges):
        vertex1, vertex2 = map(int, input().split())
        graph[vertex1].append(vertex2)
        graph[vertex2].append(vertex1)

    # 완성된 그래프 반환
    return graph


# 그래프의 시작점, 그래프를 전달
def is_binary_graph(start, visited, graph, group):
    visited[start] = group

    for neighbor in graph[start]:
        if visited[neighbor] == 0:
            result = is_binary_graph(neighbor, visited, graph, -group)
            if not result:
                return False
        else:
            if visited[neighbor] == group:
                return False
    return True


for _ in range(n):
    vertex, edge = map(int, input().split())
    graph = make_graph(vertex, edge)
    visited = [0] * (vertex + 1)
    is_bipartite = True
    for i in range(1, vertex+1):
        if visited[i] == 0:
            result = is_binary_graph(i, visited, graph, 1)
            if not result:
                is_bipartite = False
                break
    print("YES" if is_bipartite else "NO")

다른분들중에 크루스칼 알고리즘을 풀이한 사람이 있다고 해서 내일 참고해봐야겠다.

 

3. 18352 특정 거리의 도시 찾기

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


def dijkstra(start_vertex):
    pq = []
    heapq.heappush(pq, (0, start_vertex))
    distance[start_vertex] = 0

    while pq:
        cur_cost, cur_vertex = heapq.heappop(pq)
        if distance[cur_vertex] < cur_cost:
            continue
        for vertex in graph[cur_vertex]:
            cost = cur_cost + vertex[1]
            if cost < distance[vertex[0]]:
                distance[vertex[0]] = cost
                heapq.heappush(pq, (cost, vertex[0]))


vertices, edges, target, start_vertex = map(int, input().split())

fixed = [False] * (vertices+1)
distance = [math.inf] * (vertices+1)

graph = [[] for _ in range(vertices+1)]

for _ in range(edges):
    vertex1, vertex2 = map(int, input().split())
    # 연결된 정점과 cost를 등록
    graph[vertex1].append((vertex2, 1))


dijkstra(start_vertex)

if target in distance:
    for i in range(1, vertices+1):
        if distance[i] == target:
            print(i)
else:
    print(-1)

다익스트라 알고리즘을 통해 풀이했음. 구현은 처음 해봐서 많이 애먹었다.

 

 

돌아온 알고리즘 기간.. 머리 터질것같아용