18352. 특정 거리의 도시 찾기

문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예제 입력 1

4 4 2 1
1 2
1 3
2 3
2 4

예제 출력 1

4

예제 입력 2

4 3 2 1
1 2
1 3
1 4

예제 출력 2

-1

예제 입력 3

4 4 1 1
1 2
1 3
2 3
2 4

예제 출력 3

2
3

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 최단 경로

코드 - python3 성공

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

# 입력 및 초기화
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]  # 각 노드에서 이동 가능한 노드들의 리스트를 저장하는 인접 리스트
distance = [0] * (n+1)  # 시작 노드로부터의 거리를 저장하는 리스트
visited = [False] * (n+1)  # 각 노드의 방문 여부를 나타내는 리스트

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# BFS 함수
def bfs(start):
    answer = []  # 거리가 k인 노드들을 저장할 리스트
    q = deque([start])  # BFS를 위한 큐 초기화
    visited[start] = True
    distance[start] = 0

    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                distance[i] = distance[now] + 1
                if distance[i] == k:
                    answer.append(i)

    if len(answer) == 0:
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i, end='\n')

# BFS 함수 호출
bfs(x)

pro. 방금그곡

문제

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

• 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
• 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
• 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
• 음악이 00:00를 넘겨서까지 재생되는 일은 없다.
• 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
• 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

입력 형식

입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.

• m은 음 1개 이상 1439개 이하로 구성되어 있다.
• musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.
  • 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
  • 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
  • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

출력 형식

조건과 일치하는 음악 제목을 출력한다.

입출력 예시

m	musicinfos	answer
"ABCDEFG"	["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"HELLO"
"CC#BCC#BCC#BCC#B"	["03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"]	"FOO"
"ABC"	["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"WORLD"

설명

첫 번째 예시에서 HELLO는 길이가 7분이지만 12:00부터 12:14까지 재생되었으므로 실제로 CDEFGABCDEFGAB로 재생되었고, 이 중에 기억한 멜로디인 ABCDEFG가 들어있다.
세 번째 예시에서 HELLO는 C#DEFGABC#DEFGAB로, WORLD는 ABCDE로 재생되었다. HELLO 안에 있는 ABC#은 기억한 멜로디인 ABC와 일치하지 않고, WORLD 안에 있는 ABC가 기억한 멜로디와 일치한다.

코드 - python3 성공

def time_c(t):  # 시간을 분 단위로 계산하는 함수
    return int(t.split(':')[0]) * 60 + int(t.split(':')[1])


def change(x):  # 음 치환 함수
    exc = {'C#': '1', 'D#': '2', 'F#': '3', 'G#': '4', 'A#': '5'}
    for k, v in exc.items():
        x = x.replace(k, v)
    return x


def solution(m, musicinfos):
    answer = []

    # 각 음악 정보에 대해 확인
    for info in musicinfos:
        info = info.split(',')
        info[3] = change(info[3])  # 음계 치환

        # 재생 시간 계산
        T = time_c(info[1]) - time_c(info[0])

        # 실제 재생된 음악 문자열 생성
        if T >= len(info[3]):
            M = info[3] * (T // len(info[3])) + info[3][:T % len(info[3])]
        else:
            M = info[3][:T]

        # 들은 음악이 재생된 음악에 포함되어 있는지 확인
        if change(m) in M:
            answer.append([T, info[2]])

    # 조건에 맞는 음악이 없을 경우 '(None)' 반환
    if len(answer) == 0:
        return '(None)'
    else:
        # 재생 시간이 긴 순으로 정렬하고, 재생 시간이 같을 경우 먼저 입력된 음악 제목을 반환
        return sorted(answer, key=lambda x: -x[0])[0][1]

pro. 두 원 사이의 정수 쌍

문제 설명

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.

제한 사항

• 1 ≤ r1 < r2 ≤ 1,000,000

입출력 예

r1	r2	result
2	3	20

입출력 예 설명

그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.

코드 - python3 성공

import math
import sys
input = sys.stdin.readline

def solution(r1, r2):
    answer = 0

    # i는 원의 반지름을 나타냄
    for i in range(1, r2+1):
        if i < r1:
            # i가 r1보다 작으면 중심이 (0, 0)인 원 내부에 위치하는 부분 계산
            s = math.ceil(math.sqrt((r1**2 - i**2)))
        else:
            s = 0

        # 중심이 (0, 0)인 원 내에서 i에 대한 가능한 높이 계산
        e = int(math.sqrt((r2**2 - i**2)))

        # 가능한 높이의 범위를 더하여 answer에 누적
        answer = answer + e - s + 1

    # 모든 경우의 수를 고려하므로 4를 곱하여 결과 반환
    return answer * 4

20002. 사과나무

문제

N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.

농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.

하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.

그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.

악독한 땅주인 신영이로부터 고통받는 귀여운 형곤이에게 최대 총이익을 안겨주고 싶은 당신, 형곤이를 도와주자!

입력

첫 번째 줄에는 과수원의 크기 N이 주어진다. (1 ≤ N ≤ 300)

두 번째 줄부터 N + 1번째 줄까지, 해당 나무를 수확했을 때 얻을 수 있는 총이익을 표시한다.

총이익은 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫 번째 줄에 최댓값을 출력한다.

예제 입력 1

4
-1 -2 -3 -4
5 6 7 8
9 10 11 12
-13 -14 -15 -16

예제 출력 1

45

예제 입력 2

3
-1 -1 -1
-1 -1 -1
-1 -1 -1

예제 출력 2

-1

알고리즘 분류

• 브루트포스 알고리즘
• 누적 합

코드 - pypy 성공

import sys
input = sys.stdin.readline

# 입력
N = int(input())

# 정사각 크기의 누적합을 저장할 2차원 배열
prefix = [[0]*(N+1) for _ in range(N+1)]

# 누적합 계산
for i in range(1, N+1):
    data = list(map(int, input().split()))
    for j in range(1, N+1):
        prefix[i][j] = prefix[i][j-1] + prefix[i-1][j] - prefix[i-1][j-1] + data[j-1]

# 최댓값을 저장할 변수 초기화
answer = -1001

# 정사각형의 크기를 변화시켜가며 최댓값 찾기
for k in range(N):
    for r in range(1, N-k+1):      # row
        for c in range(1, N-k+1):  # col
            # (r, c) ~ (r+k, c+k) 정사각형일 때의 누적합 계산
            current_sum = prefix[r+k][c+k] - prefix[r-1][c+k] - prefix[r+k][c-1] + prefix[r-1][c-1]
            
            # 최댓값 갱신
            answer = max(answer, current_sum)

# 최댓값 출력
print(answer)