문제 1. UXUI 디자이너

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
event = [0] * (N + 1)
for _ in range(M):
	user = list(map(int, input().split()))
	for i in range(1, user[0] + 1):
		event[user[i]] += 1

max_cnt = max(event)
result = [i for i in range(N, 0, -1) if event[i] == max_cnt]
print(*result)

문제 2. 퍼져나가는 소문

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

def BFS(graph):
	queue = deque([1])
	visited = [False] * (N + 1)
	visited[1] = True
	cnt = 1
	
	while queue:
		n = queue.popleft()
		for x in graph[n]:
			if visited[x] == False:
				visited[x] = True
				cnt += 1
				queue.append(x)
	
	print(cnt)
		
		
N = int(input())
M = int(input())
graph = defaultdict(list)
for _ in range(M):
	u, v = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
	
BFS(graph)

문제 3. 구름이의 여행 2

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

def BFS(graph, K):
	queue = deque([K])
	visited = [0] * (N + 1)
	
	while queue:
		n = queue.popleft()
		for x in graph[n]:
			if x == K:
				return visited[n] + 1
			if visited[x] == 0:
				visited[x] = visited[n] + 1
				queue.append(x)
	
	return -1
		
		
N, M, K = map(int, input().split())
graph = defaultdict(list)
for _ in range(M):
	a, b = map(int, input().split())
	graph[a].append(b)

print(BFS(graph, K))

문제 4. 이상한 미로 (FAIL 8개)

구름 서비스 로그인

BFS ?

→ 가중치가 있는 경우 단순 BFS를 이용해서 최단 거리를 구할 수 없다 !!!

다익스트라 알고리즘?

어떤 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

• 그래프에 음수 가중치를 가진 간선이 존재하지 않을 때만 동작

# 문제 4. 이상한 미로 (FAIL 8개)
# DFS / 사이클 판단

import sys
import heapq
from collections import defaultdict

input = sys.stdin.readline

def Dijkstra(graph, N, A):
	heap = [(0, 1, 0)]
	visited = [0] * (N + 1)
	visited[1] = -1

	while heap:
		w, n, prev = heapq.heappop(heap)
		if n == N:
			continue
		if w < visited[n]:
			continue
		for x, xw in graph[n]:  # sorted(graph[n], key = lambda x: x[1])
			if visited[x] == 0 or w + xw < visited[x]:
				if prev == 0 or prev % A[n - 1] == x % A[n - 1]:
					visited[x] = w + xw
					heapq.heappush(heap, (w + xw, x, n))

	return visited[N] if visited[N] != 0 else -1

N, M = map(int, input().split())
A = list(map(int, input().split()))
graph = defaultdict(list)
for _ in range(M):
	u, v, w = map(int, input().split())
	graph[u].append((v, w))
	graph[v].append((u, w))

print(Dijkstra(graph, N, A))