say repository

p263

전보 문제

# 이코테 p262
# 전보
import sys
import heapq
INF = int(1e9)
n, m, c = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int,sys.stdin.readline().split())
    graph[x].append((y,z))
distance = [INF] * (n+1)

def dijkstra(start):
    q = []
    # 시작 노드로 가기위한 최단 경로 0
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            y, z = i[0], i[1] #y가 노드 z가 비용
            cost = dist + z
            if cost < distance[y]:
                distance[y] = cost
                heapq.heappush(q, (cost, y))
dijkstra(c)
cnt = 0
max_distance = 0
for d in distance:
    if d != INF:
        cnt += 1
        max_distance = max(max_distance, d)
print(cnt-1, max_distance)

# 11401
import sys
INF = int(1e9)
n = int(sys.stdin.readline()) # 도시 (노드)
m = int(sys.stdin.readline()) # 버스 (간선)
graph = [[INF]*(n+1) for _ in range(n+1)] # 최단경로 저장

# 자기 자신 지나는 경로 0으로 초기화
for a in range(1,n+1):
    for b in range(1,n+1):
        if a==b:
            graph[a][b] = 0

for _ in range(m):
    a, b, c = map(int,sys.stdin.readline().split())
    # 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
    # graph[a][b] = c
    graph[a][b] = min(graph[a][b],c)

# 플로이드 워셜 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

# 최단경로 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF: # 갈 수 없다면 0으로 출력
            print(0, end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

풀이

시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것에 주의해서

플로이드 워셜 알고리즘을 수행하면 된다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

# 14502
import sys
from collections import deque
import copy

def bfs():
    q = deque()
    tmp_graph = copy.deepcopy(graph) # 벽 설치 그래프 깊은 복사
    for i in range(N):
        for j in range(M):
            if tmp_graph[i][j] == 2: # 바이러스 있는 좌표만 큐에 넣기
                q.append((i,j))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                q.append((nx, ny))
    # 안전영역 ( 0인 칸 세기 )
    cnt0 = 0
    global answer
    for i in range(N):
        cnt0 += tmp_graph[i].count(0)
    answer = max(answer, cnt0)


def newwall(cnt):
    if cnt == 3:
        bfs() #벽 3개 새롭게 만들면 bfs 진행
        return #재귀함수로 돌아가서 벽 없애고 다시 재귀함수 
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                graph[i][j] = 1 # 빈 칸이면 벽 설치
                newwall(cnt+1) # 벽 설치 재귀함수
                graph[i][j] = 0

N, M = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
answer = 0
newwall(0) #벽 만들기
print(answer)

풀이

바이러스(2) 주변에서 빈칸(0) 중 3개를 선택해 벽(1)을 세우고 bfs로 바이러스가 퍼질 때, 0의 개수 중 최댓값을 구한다.

벽을 3개 세우는 모든 경우의 수에 bfs를 실행시켜 최대값을 구해야 한다.

이때, 경우의 수마다 bfs 실행 시, copy 라이브러리의 deepcopy를 사용한다.

# 12865
# 냅색 알고리즘
import sys
n, k = map(int,sys.stdin.readline().split())
knapsack = [[0 for _ in range(k+1)] for _ in range(n+1)]
stuff = [[0,0]]
for _ in range(n):
    stuff.append(list(map(int,sys.stdin.readline().split())))

for i in range(n+1):
    for j in range(k+1):
        weight = stuff[i][0]
        value = stuff[i][1]

        if j < weight: # 버틸 수 있는 무게가 현재 무게보다 작다면 전에 있는 값 그대로
            knapsack[i][j] = knapsack[i-1][j]
        else:
            # max( 현재 물건을 넣어주고 남은 무게를 채울 수 있는 최대값 / 다른 물건들로 채우는 값 )
            knapsack[i][j] = max(value + knapsack[i-1][j-weight], knapsack[i-1][j])
print(knapsack[n][k])

풀이

냅색 알고리즘이다. 

현재 물건이 현재 돌고 있는 무게보다 작다면,

바로 [이전물건][같은무게] 값을 가져온다.

현재 물건이 현재 돌고 있는 무게보다 크다면,

max(현재 물건을 넣어주고 남은 무게를 채울 수 있는 최대값, 다른 물건으로 채우는 값) 을 knapsack[i][j]에 삽입한다.

최종적으로 knapsack[n][k] 출력하면 무게가 k일 때의 최대 값을 출력할 수 있다.

import sys
import heapq
n, k = map(int,sys.stdin.readline().split())
q = [] # 보석 최소힙
bag = [] #가방 무게 리스트
for _ in range(n):
    heapq.heappush(q,list(map(int,sys.stdin.readline().split())))
for _ in range(k):
    bag.append(int(sys.stdin.readline()))
# 가방 오름차순 정렬
bag.sort()

result = 0
take = [] # 담은거
for c in bag:
    # 가방에 담을 수 있는 무게만 최대힙에 넣기
    while q and q[0][0] <= c:
        possible_m, possible_v = heapq.heappop(q)
        heapq.heappush(take, -possible_v)

    if take:
        result += (-heapq.heappop(take))
    elif not q:
        break
print(result)

import sys
import heapq
n = int(sys.stdin.readline())
q = []
for _ in range(n):
    heapq.heappush(q,list(map(int,sys.stdin.readline().split())))
    # 최소힙에 삽입
target, fuel = map(int,sys.stdin.readline().split())

move = [] #움직인 큐 최대힙
cnt = 0
while fuel<target:
    while q and q[0][0]<=fuel:
        mf, pf = heapq.heappop(q)
        heapq.heappush(move,[-pf,mf])

    if not move:
        cnt = -1
        break
    pf1, mf1 = heapq.heappop(move)
    fuel += -pf1
    cnt += 1
print(cnt)

풀이

그리디 알고리즘, 우선순위 큐

1km를 가는데 1L의 연료가 새 나가게 되니까 처음의 연료양으로 최종 마을까지 가야 한다.

1. 입력받은 주유소 n개의 ( 주유소 거리, 연료 양 )을 최소 힙에 저장한다.
2. 처음의 연료 양을 시작으로 최종 마을까지 최소의 주유소를 거쳐 가야 한다.
3. 가는 길에 주유소가 있어야 하고 갈 수 있는 주유소에서 최대의 연료 양을 뽑아야 한다.
4. 이때, 우선순위 큐를 생각하여 최대 힙으로 바꿔야 한다.
5. 그중에서도 연료 양이 기준이 되기에 (연료 양, 주유소 거리) 순서를 바꿔주고 ( - 연료양, 주유소거리 )로 연료 양에 -를 붙여서 최대 힙을 만든다. 

출처 : 백준

문제

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다.

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x<p, y<q 이다. 예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다. 

먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

그림 (a)

또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다. 

그림 (b)

그림 (c)

마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

그림 (d)

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다. 

공통부분의 특성코드 문자

직사각형	a
선분	b
점	c
공통부분이 없음	d

코드1

#2527
import sys
for i in range(4):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int,sys.stdin.readline().split())
    # 직사각형이 겹치기 위한 계산
    # 왼쪽 변
    xl = max(x1, x3)
    # 오른쪽 변
    xr = min(x2, x4)
    # 윗 변
    upr = min(y2,y4)
    # 아랫 변
    downl = max(y1, y3)

    #겹치는 부분 (차이)
    diffx = xr-xl
    diffy = upr-downl

    # 차이가 둘다 양수면 겹치는 부분이 직사각형
    if diffx > 0 and diffy > 0:
        print("a")
    # 둘 다 0이면 점
    elif diffx == 0 and diffy == 0:
        print("c")
    # 공통부분이 없음
    elif diffx < 0 or diffy < 0:
        print("d")
    else: # 선분
        print("b")

코드2

#2527
import sys
for i in range(4):
    x1, y1, p1, q1, x2, y2, p2, q2 = map(int,sys.stdin.readline().split())

    if p1 < x2 or q1 < y2 or p2 < x1 or q2 < y1:
        #겹치지 않음
        print("d")
        continue
    elif p1 == x2 or p2 == x1:
        if q1 == y2 or q2 == y1:
            print("c") #점
            continue
        else:
            print("b") #선분
            continue
    elif q1 == y2 or q2 == y1:
        print("b")
        continue
    else:
        print("a") #직사각형
        continue