백준(2252, 1516,1948)

5 분 소요

위상정렬

줄세우기(2252)

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

입출력 예시

2
3
3

--------------

2 3

해결책

이문제는 학생들의 키를 비교할 수 있는 정보를 일부 제공하는데, 그정보만으로 키의 순서를 결정해야하는 문제이다. 즉 위상정렬 구현만으로 쉽게 해결 할 수 있다.

maps를 구성한다. ( 입력정보로부터)
degree를 계산한다 (진입차수를 계산한다.)

2.1 degree가 0인 노드들을 큐에 진입시킨다.
큐를 dequeue하면서 출력하고 진입차수 값들을 감소 시켜주면서 큐에 enqueue시켜주면 간단히 해결할 수 있다.

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int,input().split())

maps = [[] for _ in range(n+1)]

deg=[0]*(n+1)

for i in range(m):
    s, e = map(int,input().split())

    maps[s].append(e)
    deg[e]+=1

deq = deque([])

for i in range(1,len(deg)):
    if deg[i] ==0 :
        deq.append(i)

while deq :
    node = deq.popleft()
    print(node, end =" ")

    for j in maps[node]:
        deg[j]-=1
        if deg[j] ==0 :
            deq.append(j)

게임개발하기(1516)

숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

입력

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. 모든 건물을 짓는 것이 가능한 입력만 주어진다.

입출력 예시

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

--------------

10
20
14
18
17

해결책

“벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에” 이문장에서 선수해야하는 작업이 있다에서 위상정렬을 떠올릴 수 있고,

위의 2252번 문제와 동일하지만, n번 작업이 실행되는 시작을 기록해줘야한다.

maps를 구성한다. ( 입력정보로부터)
degree를 계산한다 (진입차수를 계산한다.)

2.1 degree가 0인 노드들을 큐에 진입시킨다.
큐를 dequeue하면서 진입차수 값들을 감소 시켜주면서 큐에 enqueue시켜준다.

3.1 작업의 시작시간을 얻기위해, 이전에 먼저끝난 작업이 기록했을 시간이 있을 수 있기때문에, 현재노드의 (작업시작시간 + 작업시간)과 해야할 작업의 작업시작시간을 비교하여 큰값을 기록해준다.

코드

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

n = int(input())

work = [0]*(n+1)

ans = [0] * (n+1)

deg = [0] * (n+1)

maps = [[] for _ in range(n+1)]

for i in range(1,n+1):
    tmp=list(map(int,input().split()))
    
    tmp.remove(-1)
    work[i]=tmp.pop(0)

    for j in tmp :
        maps[j].append(i)
        deg[i]+=1

deq=deque([])

for i in range(1,len(deg)):
    if deg[i] == 0:
        deq.append(i)

while deq :
    node = deq.popleft()

    for j in maps[node]:

        ans[j]=max(ans[j] , ans[node]+work[node])
        deg[j]-=1

        if deg[j]==0 :
            deq.append(j)
        
        
for i in range(1,len(ans)):
    ans[i] +=work[i]
    print(ans[i])

임계경로 구하기(1948)

월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.

이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.

어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라.

출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

입력

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다.

그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.

모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

입출력 예시

7
9
1 2 4
1 3 2
1 4 3
2 6 3
2 7 5
3 5 1
4 6 4
5 6 2
6 7 5
1 7

--------------

12
5

해결책

“이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가?” 모든 구성원이 만나기 위한 최소시간은 어떤 경로로 오든 가장 오랜시간이 걸리는 사람이 도착지에 도착해야하므로, 최장으로 걸리는 사람의 시간을 기록해야한다.

또한 한번도 쉬지 않고 달리는 사람의 거치는 도로의 개수를 구하라했으므로, 위상정렬의 거리를 기록하는 리스트에서 도착지에서 역방향으로 도로의 가중치값을 뺐을때, 거리 리스트의 값과 일치하는 도로의 개수를 카운팅해주면된다.

A. 최장시간 구하기

maps를 구성한다. ( 입력정보로부터)
degree를 계산한다 (진입차수를 계산한다.)

2.1 degree가 0인 노드들을 큐에 진입시
큐를 dequeue하면서 진입차수 값들을 감소 시켜주면서 큐에 enqueue시켜준다.

3.1 작업의 시작시간을 얻기위해, 이전에 먼저끝난 작업이 기록했을 시간이 있을 수 있기때문에, 현재노드의 (작업시작시간 + 작업시간)과 해야할 작업의 작업시작시간을 비교하여 큰값을 기록해준다.

B. 한번도 쉬지 않고, 달리는 도로의 개수를 구하라.

큐에 도착노드를 진입시킨다.
큐가 not empty할동안

2.1 dequeue를 한 후, 루프를 돈다.

2.2 next노드의 임계경로값이 present노드의 임계경로값 - next노드로 가는 가중치 값이 일치하면 counting해준다.

2.3 next노드가 방문되었는지 확인 후 방문되지 않았으면 진입, 방문되었으면 진입시키지 않는다. ( 최초 1회만 큐에 진입시켜도 된다. 우리는 도로의 개수를 세는것이기 때문에 중복해서 큐에 진입시켜 중복계산할 필요가 없다.)

코드

from collections import deque
import sys
import math

input = sys.stdin.readline

n = int(input())

m = int(input())

res1=0
visited=[0] * (n+1)
maps = [ [] for _ in range(n+1)]
rmaps = [ [] for _ in range(n+1)]

cpath = [0] * (n+1)

degree = [0] * (n+1)

for i in range(m):
    st,end,weight = map(int,input().split())

    maps[st].append([end, weight])
    rmaps[end].append([st, weight])
    degree[end]+=1
    
snode,enode = map(int,input().split())

deq=deque([])

for i in range(1,n+1) :
    
    if degree[i] ==0 :
        deq.append(i)

while deq :
    pnode = deq.popleft()

    for nnode in maps[pnode]:
        
        degree[nnode[0]]-=1
        cpath[nnode[0]]=max(cpath[nnode[0]] , cpath[pnode]+nnode[1])
        if degree[nnode[0]]==0:
                  
                  deq.append(nnode[0])
 
res1= cpath[enode]

deq=deque([])

cnt =0

deq.append(enode)
visited[enode]=1
while deq :
    pnode = deq.popleft()

    for nnode in rmaps[pnode]:
        
        if  cpath[pnode]-nnode[1] == cpath[nnode[0]]:
            
            cnt+=1
            if visited[nnode[0]] == 0 :
                
                visited[nnode[0]] =1
                deq.append(nnode[0])
                
print(res1)
print(cnt)

Twitter Facebook LinkedIn

최종원

백준(2252, 1516,1948)

위상정렬

줄세우기(2252)

해결책

코드

게임개발하기(1516)

해결책

코드

임계경로 구하기(1948)

해결책

코드

공유하기

댓글남기기

참고

NMT - with Attention

L layer NN - with ReLu

L layer NN - Cat Recognition

Transformers Architecture with TensorFlow