첫째 줄에 도시의 개수 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)

출력

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

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

단방향 그래프에서 특정 노드로부터의 최단 거리를 구하는 문제이다. 모든 간선의 가중치가 1이므로 BFS 또는 다익스트라로 해결할 수 있다.

import heapq
from collections import defaultdict

INF = float("inf")

N, M, K, X = map(int, input().split())

graph = defaultdict(list)

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


def dijkstra(start):
    dist_list = [INF] * (N + 1)
    dist_list[start] = 0
    q = [(0, start)]

    while q:
        dist, cur_node = heapq.heappop(q)
        if dist_list[cur_node] < dist:
            continue

        for n_node in graph[cur_node]:
            if dist + 1 < dist_list[n_node]:
                dist_list[n_node] = dist + 1
                heapq.heappush(q, (dist + 1, n_node))

    return dist_list


inf_cnt = 0
for node, dist in enumerate(dijkstra(X)[1:], start=1):
    if dist == K:
        print(node)
    else:
        inf_cnt += 1

if inf_cnt == N:
    print(-1)

• 각 컴퓨터마다 BFS: O(N + M)
• 전체 N개 컴퓨터: O(N × (N + M))
• N ≤ 10,000, M ≤ 100,000
• 최악의 경우: 10,000 × 110,000 = 1,100,000,000

시간 제한이 5초이고, 파이썬은 초당 약 1억 번 연산이 가능하므로 통과 가능하다.

시간이 빡빡할 경우 다음 최적화를 고려할 수 있다:

1. 빠른 입출력: sys.stdin.readline() 사용

2. DFS 대신 BFS: 재귀 오버헤드 감소

3. 조기 종료: 이미 방문한 노드 재탐색 방지

4. 역방향 그래프: A→B가 아닌 B→A로 저장

5. 자기 자신 포함: 해킹한 컴퓨터 자신도 카운트에 포함

6. 오름차순 출력: 여러 개일 경우 정렬 필요

7. 빠른 입출력: N, M이 크므로 필수

이 문제는 “신뢰 관계”를 반대로 생각해야 한다:

• “A가 B를 신뢰” ≠ A를 해킹하면 B도 해킹됨 (X)
• “A가 B를 신뢰” = B를 해킹하면 A도 해킹됨 (O)

N, K = map(int, input().split())
distance = [float('inf')] * 100001

def bfs_01(start):
    dq = deque([(0, start)])
    distance[start] = 0
    
    while dq:
        dist, c = dq.popleft()
        
        if distance[c] < dist:
            continue
            
        # 비용 0인 간선 (순간이동)
        n = c * 2
        if 0 <= n <= 100000 and dist < distance[n]:
            distance[n] = dist
            dq.appendleft((dist, n))  # 앞에 추가
        
        # 비용 1인 간선 (걷기)
        for n in (c + 1, c - 1):
            if 0 <= n <= 100000 and dist + 1 < distance[n]:
                distance[n] = dist + 1
                dq.append((dist + 1, n))  # 뒤에 추가

bfs_01(N)
print(distance[K])

1. (0, 0)에서 시작
2. 오른쪽(→), 아래(↓) 방향으로만 이동
3. 값이 1인 칸만 이동 가능
4. (M-1, N-1)에 도달하면 성공

from collections import deque

N, M = map(int, input().split())

space = [list(map(int, input().split())) for _ in range(M)]

dyx = ((1, 0), (0, 1))

q = deque([(0, 0)])
visited = set([(0, 0)])

is_possible = False

if N == 1 and M == 1:
    is_possible = True

while q:
    y, x = q.popleft()
    for dy, dx in dyx:
        ny, nx = y + dy, x + dx
        if not(0 <= ny < M and 0 <= nx < N):
            continue
        if space[ny][nx] == 0:
            continue
        if (ny, nx) in visited:
            continue
        if (ny, nx) == (M - 1, N - 1):
            is_possible = True
            break

        q.append((ny, nx))
        visited.add((ny, nx))
    else:
        continue
    break

# print(visited)
print('Yes' if is_possible else 'No')

class Network:

    def __init__(self, N, M):
        self.N, self.M = N, M
        self.cnt = 0
        self.visited = [False] * (N + 1)
        self.visited[1] = True
        self.network = defaultdict(list)
        self._make_network()

    def _make_network(self):
        for _ in range(self.M):
            s, e = map(int, input().split())
            self.network[s].append(e)
            self.network[e].append(s)

    def search_computer(self, node=1):
        for n_node in self.network[node]:
            if self.visited[n_node]:
                continue
            self.visited[n_node] = True
            self.cnt += 1
            self.search_computer(n_node)


def main():
    N = int(input())
    M = int(input())

    network = Network(N, M)
    network.search_computer()
    print(network.cnt)


if __name__ == "__main__":
    main()

첫째 줄에 동영상의 개수 N (1 ≤ N ≤ 5,000)과 질문의 개수 Q (1 ≤ Q ≤ 5,000)가 주어진다.

다음 N-1개의 줄에는 두 동영상을 연결하는 간선 정보 p, q, r이 주어진다. 이는 동영상 p와 동영상 q가 연관도 r로 연결되어 있음을 의미한다. (1 ≤ r ≤ 1,000,000,000)

다음 Q개의 줄에는 k, v가 주어진다. 이는 유사도가 k 이상인 동영상을 동영상 v를 기준으로 찾는 질의이다.

출력

Q개의 줄에 각 질문에 대한 답변을 출력한다.

이 문제는 트리 구조에서 특정 노드로부터 도달 가능한 노드들 중 경로상의 최소 가중치가 특정 값 이상인 노드의 개수를 세는 문제이다.

두 동영상 간의 유사도는 경로상의 최소 연관도이다. 따라서 시작 노드에서 BFS/DFS를 수행하며, 각 노드까지의 경로에서의 최소값을 유지하면서 탐색한다.

풀이 1: BFS를 이용한 방법

각 쿼리마다 BFS를 수행하여 유사도가 k 이상인 노드를 센다.

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

이 문제는 시뮬레이션과 BFS를 결합한 문제이다. 매일 국경선이 열리는 나라들을 찾아 연합을 만들고, 인구를 재분배하는 과정을 반복해야 한다.

인구 이동이 일어나는 하루는 다음과 같은 과정을 거친다:

1. 연합 찾기: BFS를 사용하여 국경선이 열리는 나라들의 연합을 찾는다.
2. 인구 재분배: 각 연합의 평균 인구수를 계산하고 재분배한다.
3. 종료 조건 확인: 어떤 연합도 만들어지지 않으면 인구 이동 종료.

1. 연합 찾기 (open 함수)

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 ’.’, ’#’, ‘O’, ‘R’, ‘B’ 로 이루어져 있다. ’.’은 빈 칸을 의미하고, ’#‘은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, ‘O’는 구멍의 위치를 의미한다. ‘R’은 빨간 구슬의 위치, ‘B’는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 ’#‘이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

맵을 BFS로 탐색하면서 시뮬레이션 하는 문제이다.

처음 시도한 방식은 정말 단순하게 모두 다 구현하는 것으로 맵 리스트 자체에서 구슬들을 실제로 움직이는 것까지 구현하였다.