현제의 현재이야기

저번에 연결요소와 같은 그래프 탐색 문제이다. 백준 풀다가 dfs의 감을 다시 잡기 위해서 기본 개념문제를 풀어보았다. 1에서 부터 탐색을 시행했을 때, 1으로 부터 시작된 서로 다른 연결 요소의 개수를 물어보는 문제. n, m = tuple(map(int, input().split())) graph = [ [] for _ in range(n + 1) ] visited = [False] * (n + 1) for _ in range(m): x, y = tuple(map(int, input().split())) graph[x].append(y) graph[y].append(x) cnt = 0 def dfs(v): global cnt visited[v] = True for i in graph[v]: if vi..

n, m = tuple(map(int, input().split())) input_a = list(input()) a = [] for _ in range(n): a.append(input_a.pop()) b = list(input()) t = int(input()) arr = a + b check = n * '0' + m * '1' + '9' check_arr = [] target = [] for i in check: check_arr.append(i) for _ in range(t): for i in range(n + m): if check_arr[i] == '0' and check_arr[i + 1] == '1': target.append(i) for j in target: arr[j], arr[j ..

import sys def dfs(node, cnt): check[node] = 1 for n in graph[node]: if check[n] == 0: cnt = dfs(n, cnt+1) return cnt for _ in range(int(sys.stdin.readline())): N, M = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N+1)] for _ in range(M): u, v = map(int, sys.stdin.readline().split()) graph[u].append(v) graph[v].append(u) check = [0]*(N+1) check[1] = 0 cnt = dfs(1, 0) print(cn..

import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [False] * (n+1) for _ in range(m): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x) def dfs(v): visited[v] = True for i in graph[v]: if visited[i] == False: visited[i] = True dfs(i) count = 0 for i in range(1, n+1): if visited[i] == ..

17451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net import sys from collections import deque input = sys.stdin.readline n = int(input()) speed = list(map(int, input().split())) earth = speed[-1] while len(speed) != 1: speed.pop() if earth > speed[-1]: if earth % speed[-1] != 0: earth = speed[-1] * ((earth // speed[-1]) + 1) else: earth = spe..

백준 11724번을 python으로 풀어보았다. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net from collections import deque node, line_num = tuple(map(int, input().split())) line = [tuple(map(int, input().split())) for _ in range(line_num)] line = deque(line) def bfs(first, line, line_num, ch..