IT-garden

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력과 출력

알고리즘 분류

다익스트라 알고리즘

정답

import sys
import heapq

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

def Dijkstra(a, K):
    dist = [INF] * len(a)  
    dist[K] = 0

    heap = []
    heapq.heappush(heap, [0, K])
    
    while heap:
        current_dist, here = heapq.heappop(heap)
        for there, length in a[here].items():
            next_dist = dist[here] + length

            if next_dist < dist[there]:
                dist[there] = next_dist
                heapq.heappush(heap, [next_dist, there])

    return dist

V, E = map(int, input().split())
K = int(input())
a = [{} for _ in range(V + 1)]

for i in range(E):
    u, v, w = map(int, input().split())

    if v in a[u]:
        a[u][v] = min(a[u][v], w)
    else:
        a[u][v] = w

dist=Dijkstra(a, K)

for d in dist[1:]:
    print(d if d != INF else "INF")

다익스트라 알고리즘 기본 코드를 이용합니다.

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

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

def _11726(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if a[n] != 0:
        return a[n]
    
    a[n]= ( _11726(n-2) + _11726(n-1) ) % 10007
    return a[n]

a=[0]*1001

n=int(input())

print(_11726(n))

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

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

t=int(input())

def _9095(n):
    if n == 1:
        return 1
    if n== 2:
        return 2
    if n ==3:
        return 4
    
    return _9095(n-1)+_9095(n-2)+_9095(n-3)

for i in range(t):
    print(_9095(int(input())))

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

문제

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

출력

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

예제 입력과 출력

알고리즘 분류

버블 정렬

정답

import sys

n=sys.stdin.readline().split()

for j in range(len(n)):
    for i in range(1,len(n)):
        if n[i] < n[i-1]:
            n[i], n[i-1] = n[i-1], n[i]
            print(' '.join(n))

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

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

n=input()
a=0
i=0

while True:
    if i >= len(n):
        break
    
    if n[i:i+4] == 'XXXX':
        i=i+4
        n=n.replace('X','A',4)
    elif n[i:i+2] == 'XX':
        i=i+2
        n=n.replace('X','B',2)
    elif n[i] == '.':
        i=i+1
    else:
        n=-1
        break
        
print(n)

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

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

예제 입력과 출력

알고리즘 분류

BFS

DFS

다익스트라 알고리즘

정답

from collections import deque

def bfs(sz,sx,sy):
    de=deque()
    de.append([sz,sx,sy])
    ch[sz][sx][sy] = 0

    while de:
        z, x, y = de.popleft()

        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
               
            if 0 <= nz < l and 0 <= nx < r and 0 <= ny < c:
                if a[nz][nx][ny] == 'E':
                    print('Escaped in', ch[z][x][y] + 1 ,'minute(s).')
                    return 
                    
                if ch[nz][nx][ny] == -1 and a[nz][nx][ny] == '.':
                    ch[nz][nx][ny]= ch[z][x][y] + 1
                    de.append([nz,nx,ny])
                    
    print('Trapped!')

dx = [-1,0,1,0,0,0]
dy = [0,1,0,-1,0,0]
dz = [0,0,0,0,1,-1]

while True:
    
    l,r,c=map(int,input().split())

    if l == 0 and r == 0 and c == 0:
        break
    
    a=[[[]*c for i in range(r)] for j in range(l)]
    ch=[[[-1]*c for i in range(r)] for j in range(l)]

    for i in range(l):
        a[i]=[list(input()) for i in range(r)]
        input()
   
    for i in range(l):
        for j in range(r):
            for k in range(c):
                if a[i][j][k] == 'S':
                    bfs(i,j,k)

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