IT-garden

문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2<=N<=500)과 두 학생 키를 비교한 횟수 M (0<=M<=N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

import sys
input = lambda : sys.stdin.readline().strip()

INF=sys.maxsize

n,m=map(int,input().split())
li=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    a, b=map(int, input().split())
    li[a][b] = 1

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                continue
            
            if li[i][k] == 1 and li[k][j] == 1:
                li[i][j] = 1

r=0
for i in range(1,n+1):
    c = 0
    for j in range(1, n+1):
        c += li[i][j] + li[j][i] 
    if c == n-1: #자기빼고 다 아는 경우
        r += 1
print(r)

시간 초과로 PyPy3로 제출했습니다.

a 학생이 b 학생보다 작으면 li[a][b]에 1을 추가합니다.

플로이드 와샬 알고리즘을 통해 k를 거쳐서 키를 확인할 수 있으면 거리를 1로 바꿔줍니다.

li[i][j] + li[j][i]을 통해 i보다 j가 크거나 작은지 확인합니다.
자신을 제외한 다른 수들이 크거나 작은지 확인할 수 있으면 r에 1을 더해주고 전체 r을 출력합니다.

백준 알고리즘 2458번 : www.acmicpc.net/problem/2458

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다. 

예제 입력과 출력

알고리즘 분류

BFS
DFS
플로이드 와샬 알고리즘

정답

import sys

INF = sys.maxsize
input = lambda: sys.stdin.readline().strip()
t=int(input())

while t :
    n=int(input())
    a=[list(map(int, input().split())) for i in range(n+2)]
    d=[[INF] * (n+2) for i in range(n+2)]
    
    for i in range(n+2):
        for j in range(n+2):
            if i == j :
                continue
            di=abs(a[i][0]-a[j][0]) + abs(a[i][1]-a[j][1])
    
            if di <= 1000:
                d[i][j] = 1

    for k in range(n+2):
        for i in range(n+2):
            for j in range(n+2):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    if 0 <= d[0][n+1] < INF:
        print('happy')
    else:
        print('sad')
  
    t -= 1

리스트 a에 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표를 넣습니다.

각각 좌표들간의 거리를 구해서 1000이하이면 리스트 d에 1을 넣습니다.

플로이드 와샬 알고리즘 이용해 더 빠르게 갈 수 있으면 값을 바꿔줍니다.

시작에서 락 페스티벌까지 갈 수 있는 거리가 INF보다 작으면 happy를 출력하고 아니면 sad를 출력합니다.

백준 알고리즘 9205번 : https://www.acmicpc.net/problem/9205

문제

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘
그래프 이론

정답

import sys

INF=sys.maxsize

n=int(input())
m=int(input())
li=[[INF] * (n+1) for i in range(n+1)]

for i in range(m):
    a, b, c=map(int,input().split())

    if li[a][b] != 0:
        li[a][b] = min(li[a][b], c)
    else:
        li[a][b] = c

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            li[i][j] =min(li[i][j], li[i][k] + li[k][j])

            if i == j:
                li[i][j] = 0

for i in range(1,n+1):
    for j in range(1,n+1):
        if li[i][j] == INF:
            print(0, end=' ')
        else:
            print(li[i][j], end=' ')
    print()

백준 알고리즘 11404번 : https://www.acmicpc.net/problem/11404

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력과 출력

알고리즘 분류

BFS
DFS
플로이드 와샬 알고리즘

정답

import sys

INF=sys.maxsize

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] == 1 and a[k][j] == 1:
                a[i][j] = 1

for i in range(n):
    for j in range(n):
        print(a[i][j], end=' ')
    print()

백준 알고리즘 11403번 : www.acmicpc.net/problem/11403

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

다익스트라 알고리즘

정답

import sys
import heapq

input= lambda : sys.stdin.readline().strip()
INF=sys.maxsize

def _1504(s):
    dist = [INF] * len(li)
    dist[s] = 0

    queue=[]
    heapq.heappush(queue, [0, s])

    while queue:
        cd, here = heapq.heappop(queue)

        for there, length in li[here]:
            nd= dist[here] + length
            if nd < dist[there]:
                dist[there] = nd
                heapq.heappush(queue, [nd, there])
        
    return dist

n,e=map(int,input().split())
li=[[] for i in range(n+1)]

for i in range(e):
    a, b, c=map(int,input().split())

    li[a].append([b,c])
    li[b].append([a,c])

v1,v2=map(int,input().split())

one=_1504(1)
v1d=_1504(v1)
v2d=_1504(v2)

m=min(one[v1] + v1d[v2] + v2d[n], one[v2] + v2d[v1] + v1d[n])

if m < INF:
    print(m)
else:
    print(-1)

양방향 그래프라는 것을 생각해 두 곳에 거리를 넣습니다.

1 → v1 → v2 → N 경로와 1 → v2 → v1 → N 경로를 확인해서 더 작은 경로를 출력합니다.

백준 알고리즘 1504번 : https://www.acmicpc.net/problem/1504 

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘

다익스트라 알고리즘

정답

import sys
import heapq

INF=sys.maxsize

def _1238(a, s):

    dist=[INF] * len(a)
    dist[s] =0

    queue=[]
    heapq.heappush(queue, [0, s])

    while queue:
        c_d, h= heapq.heappop(queue)

        for there, length in a[h]:
            next_d = dist[h] + length

            if next_d < dist[there]:
                dist[there]=next_d
                heapq.heappush(queue, [next_d, there])

    return dist

n, m, x=map(int,input().split())
a=[[] for i in range(n+1)]

for i in range(m):
    s, e, w=map(int,input().split())
    a[s].append([e, w])

c=[]
dist_h = _1238(a,x)

for i in range(1,n+1):
    dist= _1238(a, i)
    c.append(dist[x] + dist_h[i])

print(max(c))

다익스트라 알고리즘을 여러번 사용했습니다.
처음 x를 시작점으로 하여 파티 장소에서 각 집까지 오는 거리를 구해 dist_h에 저장합니다.
그 후 1부터 n까지 각각의 집을 시작점으로 하여 다익스트라 알고리즘을 실행해 각 집에서 x까지 가는 거리를 구해주었습니다.
각자의 집에서 파티장소까지 갔다 오는 값을 더해서 가장 오래 걸리는 학생의 소요시간을 출력합니다.

백준 알고리즘 1238번 : www.acmicpc.net/problem/1238