🍀 백준 15812. 침략자 진아

문제

진아는 행성의 침략자이다. 진아의 행성 침략 방법은 너무 끔찍하기로 소문이 나 있다.

진아는 2개의 독주머니를 가지고 있는데, 독주머니는 빠른 속도로 독을 퍼트려 행성에 있는 생물을 중독시킨다고 한다. 독주머니의 독은 1초마다 인접한 지역으로 퍼질 정도로 빠르다! 진아는 바쁘기 때문에 아주 빠르게 행성을 침략하고자 한다.

당신은 진아의 조수이다. 진아는 포악하기 때문에 독주머니를 설치할 최적의 위치를 알려주지 않는다면 고문을 당할 수도 있다! 진아에게 최적의 위치에 설치한다면 몇 초 만에 모든 마을에 독이 퍼질 수 있을지 알려주자.

먼저 2차원 지도에 마을들의 위치가 주어진다. 예를 들어 행성의 지도가 다음과 같이 주어졌을 때,

5 6
110011
000000
000000
011010
000000

맨 위의 가장 왼쪽이 0,0 이라고 할 때 (2,1) 과 (2,4) 에 독주머니를 설치한다면 3초 만에 모든 마을이 중독된다. (2, 1)은 3번째 줄의 2번째 칸이다. (행성 전체가 중독되는데 걸리는 시간을 구하는 것이 아니라 모든 마을이 중독되는데 걸리는 시간을 묻는 것이다.)

단, 독주머니를 마을에는 둘 수 없다. 빈 공간에만 둘 수 있다. 마을에 독주머니를 뒀다간 들킬 수도 있기 때문이다.

또한, A라는 마을과 B라는 마을이 인접해있고 A라는 마을이 중독되었다면 1초 후에 B라는 마을로 전염된다. (이 문제에서 인접이란 상하좌우를 뜻한다.)

입력

2차원 공간의 세로의 크기와 가로의 크기를 의미하는 두 정수 N, M(2 ≤ N, M ≤ 20)이 주어진다.

예제 입력과 같이 마을의 지도가 주어진다. 0은 빈 공간을, 1은 마을이 있는 공간을 의미한다.

출력

가장 최적의 위치 두 곳에 독주머니를 설치 시, 몇 초 만에 행성을 초토화 시킬 수 있는지 출력하시오.

단, 독주머니를 설치하지 못하는 경우는 없다.

예제 입력 1

5 6
110011
000000
000000
011010
000000

예제 출력 1

3

예제 입력 2

19 18
001010001000011000
000000100110010100
000001000110110000
001000000000000100
000000010011000010
100101010010000100
010000110101100001
000100001001101001
101001110100100000
001000100000010000
010011101101000100
100001100110010001
010010110100000001
001001000000100000
000000000000101010
101010000001101111
011110000000000111
000000001010100000
001100010110000000

예제 출력 2

12

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
house = []
space = []
ans = 400 # 20 * 20

for r in range(N): # 지도 입력받기
    row = list(input())
    for c in range(M): # 마을이 있는 곳과 없는 곳 좌표값 저장
        if row[c] == '1':
            house.append((r, c))
        else:
            space.append((r, c))

# 최단 거리 계산
for s1 in range(len(space)):
    for s2 in range(s1 + 1, len(space)):
        max_cst = 0
        for h in house:
            dist_s1_h = abs(space[s1][0] - h[0]) + abs(space[s1][1] - h[1]) # 독주머니1 - 마을
            dist_s2_h = abs(space[s2][0] - h[0]) + abs(space[s2][1] - h[1]) # 독주머니2 - 마을
            max_cst = max(max_cst, min(dist_s1_h, dist_s2_h)) # 둘 중에 더 거리가 긴 것

            if max_cst > ans: # ans 보다 현재 값이 더 크면 정답 x
                break

        ans = min(ans, max_cst) # 최솟값 갱신

print(ans)

🍀 백준 1325. 효율적인 해킹

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

예제 입력 1

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2

코드

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

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

def bfs(start):
	cnt = 1
	queue = deque([start])
	visit = [False for _ in range(n+1)]
	visit[start] = True # 첫 노드는 방문으로 표시

	while queue:
		cur = queue.popleft()

		for nx in graph[cur]:
			if not visit[nx]: # 첫방문 노드라면
				visit[nx] = True # 방문 표시
				cnt += 1 # 카운팅
				queue.append(nx) # 큐에 저장

	return cnt

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

for _ in range(m): # 신뢰관계 입력받기
	a,b = map(int,input().split())
	graph[b].append(a)

maxCnt = 1
ans = []

for i in range(1,n+1):
	cnt = bfs(i) # bfs 얻은 값 비교
	if cnt > maxCnt: # 최댓값 갱신
		maxCnt = cnt
		ans.clear() # 초기화
		ans.append(i) # 새 값으로 갱신
	elif cnt == maxCnt:
		ans.append(i)

print(ans)

🍀 백준 1911. 흙길 보수하기

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

예제 입력 1

3 3
1 6
13 17
8 12

예제 출력 1

5

힌트

아래와 같이 5개의 널빤지가 필요하다.

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표

코드

import sys
input = sys.stdin.readline

n, L = map(int, input().split())
pools = [list(map(int, input().split())) for _ in range(n)] # 웅덩이 정보
# 웅덩이 좌표 오름차순 정렬
pools.sort(key=lambda x:x[0])

# 웅덩이를 덮은 마지막 널빤지의 위치
cur = 0
# 널빤지의 개수
cnt = 0

for start, end in pools:
    if start > end:
        continue
    # 이전 웅덩이에서 덮은 널빤지가 해당 웅덩이를 덮고있는 경우
    if cur > start:
        start = cur # 덮인 널빤지부터 시작위치를 잡고 덮는다
        
    # 널빤지의 개수 카운트
    while start < end:
        start += L
        cnt += 1
    cur = start

print(cnt)

🍀 백준 1484. 다이어트

문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

예제 입력 1

15

예제 출력 1

4
8

코드

import sys
input = sys.stdin.readline

G = int(input())

P = [x for x in range(1, 100001)]
Q = [x for x in range(1, 100001)]

N, M = 100000, 100000 # P와 Q의 길이 최댓값
left, right = 0, 0  # 투 포인터
ans = []

while left < N and right < M:
    # G는 현재 몸무게(A)의 제곱 - 성원이가 기억하고 있던 몸무게(B)의 제곱
    # G = A^2 - B^2 => (A + B)*(A - B)
    tmp = (P[left] + Q[right]) * (P[left] - Q[right])

    if tmp == G: ans.append(P[left])
    if tmp < G:
        left += 1
        continue
    else:
        right += 1

if not ans: # ans 리스트가 비어있다면
    print(-1)
else: # ans 내 요소들 출력
    for y in ans: print(y)