백준 플레를 향해서 - 12월 셋째주(12.12~12.18)

1) 백준 13549 : 숨바꼭질 3

import heapq
INF = int(1e9)
minlst = [INF]*100001

n,k = map(int,input().split())

def dijkstra(start,end):
    minlst[start] = 0
    heap = [(0,start)]
    
    while heap:
        dist,now = heapq.heappop(heap)
        
        if now == k:
            break
        elif dist > minlst[now]:
            continue
        else:
            graph = [(now-1,1),(now+1,1),(now*2,0)]
            for endPoint,w in graph:
                if endPoint >= 0 and endPoint <= 100000 and dist+w < minlst[endPoint]:
                    minlst[endPoint] = dist + w
                    heapq.heappush(heap,(minlst[endPoint],endPoint))
        
dijkstra(n,k)          
print(minlst[k])

처음엔 BFS를 먼저 생각했으나 이동할때마다 걸리는 시간이 다르므로 불가능했다.

다익스트라 알고리즘을 조금 변형해 풀 수 있었다.

 

2) 백준 11404 : 플로이드

import sys
INF = int(1e9)

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
floid = [[INF]*n for _ in range(n)]

for i in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    if c < floid[a-1][b-1]:
        floid[a-1][b-1] = c
        
    
def fw(now):
    for i in range(n):
        for j in range(n):
            if i == j:
                floid[i][j] = 0
            else:
                if floid[i][j] > floid[i][now] + floid[now][j]:
                    floid[i][j] = floid[i][now] + floid[now][j]
    
for i in range(n):
    fw(i)
    
for i in range(n):
    for j in range(n):
        if floid[i][j] == INF:
            print(0,end = " ")
        else:
            print(floid[i][j], end = " ")
    print()

한 정점에서 다른 정점으로 향하는 최단 경로를 구하는 플로이드-워셜 알고리즘을 공부하고 기본 문제를 풀어봤다.

플로이드-워셜 알고리즘의 시간복잡도가 O(N**3) 이라는 점을 기억하자

 

3) 백준 1865 : 웜홀

import sys
INF = int(1e9)

t = int(sys.stdin.readline().strip())

for i in range(t):
    n,m,w = map(int,sys.stdin.readline().strip().split())
    floid = [[INF]*n for _ in range(n)]

    for i in range(m):
        a,b,c = map(int,sys.stdin.readline().strip().split())
        if c < floid[a-1][b-1]:
            floid[a-1][b-1] = c
        if c < floid[b-1][a-1]:
            floid[b-1][a-1] = c

    for i in range(w):
        a,b,c = map(int,sys.stdin.readline().strip().split())
        c = -c
        if c < floid[a-1][b-1]:
            floid[a-1][b-1] = c
    
    def fw(now):
        for i in range(n):
            for j in range(n):
                if floid[i][j] > floid[i][now] + floid[now][j]:
                    floid[i][j] = floid[i][now] + floid[now][j]
                
                if i == j and floid[i][j] < 0:
                    return -1
        return 0
    
    answer = "NO"
    for i in range(n):
        temp = fw(i)
        if temp == -1:
            answer = "YES"
            break
    
    print(answer)

마찬가지로 플로이드-워셜 알고리즘을 이용해 푸는 문제였다.

floyd 스펠링을 몰라서 floid 라고 쓴 건 넘어가자

 

4) 백준 14500 : 테트로미노

코드 133줄짜리 구현 문제였다.

배열과 반복문을 잘 다루는게 구현 문제를 잘 푸는 방법인 것 같다.

 

5) 백준 1719 : 택배

import sys
INF = int(1e9)

n,m = map(int,sys.stdin.readline().strip().split())
graph = [[INF]*n for _ in range(n)]
answer = [["-"]*n for _ in range(n)]

for i in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    
    answer[a-1][b-1] = b
    answer[b-1][a-1] = a
    
def fw(now):
    for i in range(n):
        for j in range(n):
            if i == j:
                graph[i][j] = 0
            if graph[i][j] > graph[i][now] + graph[now][j]:
                graph[i][j] = graph[i][now] + graph[now][j]
                answer[i][j] = answer[i][now]
        
for i in range(n):
    fw(i)
    
for i in range(n):
    for j in range(n):
        print(answer[i][j] , end = " ")
    print()

마찬가지로 플로이드-워셜 알고리즘을 사용해 푸는 문제였다.

특정 정점을 거쳐갔을 때 경로가 더 짧아진다면 배열을 갱신하는 플로이드-워셜 알고리즘의 원리를 잘 기억하자

 

6) 백준 1916 : 최소비용 구하기

import sys,heapq

INF = int(1e9)
n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

graph = [[] for _ in range(n)]

for i in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    graph[a-1].append((b-1,c))
    
start,end = map(int,sys.stdin.readline().strip().split())
    
def dijkstra():
    minlst = [INF]*n
    minlst[start-1] = 0
    heap = [(0,start-1)]
    
    while heap:
        dist,now = heapq.heappop(heap)
        
        if now == end-1:
            print(dist)
            return
        elif minlst[now] < dist:
            continue
        else:
            for endPoint,w in graph[now]:
                if minlst[endPoint] > dist + w:
                    minlst[endPoint] = dist + w
                    heapq.heappush(heap,(minlst[endPoint],endPoint))
    
    
dijkstra()

간단한 다익스트라 활용문제였다

 

 

다익스트라, 플로이드-워셜 알고리즘을 이용한 문제들을 풀어봤는데

확실히 알고리즘의 기본 난이도가 높은 편이라 그런지 응용 문제들을 푸는게 굉장히 까다로워졌다.

지금 4일째 한 문제도 못 풀고 있는데 정체기가 온 것 같다.

 

2월까지 골드 1 달기로 목표를 바꿔봐야겠다.