우주의 IT 소행성

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 = [-1] * (n + 1)
distance[x] = 0  # 출발 도시에서 출발 도시까지 거리는 0

# 모든 도로 정보 입력
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

# BFS 실행
queue = deque([x])
while queue:
    now = queue.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            queue.append(next_node)

# 최단 거리가 K인 도시의 번호 오름차순 출력
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check = True

# 최단 거리가 K인 도시가 없을 때 -1 출력
if check == False:
    print(-1)

BFS를 사용하여 푼 문제

그래프에서 모든 간선의 비용이 동일할 때에는 너비 우선 탐색으로 손쉽게 해결할 수 있다.

노드의 개수 N의 최대 : 30000

간선의 개수 M의 최대 : 10000

O(N + M)으로 해결해야 하는 문제로, 특정 도시 X를 시작점으로 BFS를 수행해 모든 도시까지의 최단 거리를 계산한 후, 각 최단 거리를 하나씩 확인하며 그 값이 K인 경우에 해당 도시의 번호를 출력한다.

입력값이 0 또는 1밖에 없으니 0이나 1중 하나를 선택하여 split 해준다.

1을 split 했다고 가정했을 때

0011100010 -> '00', '', '000', '', '0'

이 되는데 이때 전체 숫자 수 에서 ''의 수를 카운트해서 빼주면 된다.

이때 0011100010보다 1100011101이 더 작을수가 있기에

그 경우의 수를 생각하여준다.

s = input()
s2 = ''

for i in s:
    if i == '0':
      s2 += '1'
    else:
        s2 += '0'

a = s.split('1')
b = s2.split('1')
result = min((len(a) - a.count('')), (len(b) - b.count('')))
print(result)