본문 바로가기

알고리즘 풀이/DFS & BFS8

[백준/파이썬] 11724번 : 연결 요소의 개수 https://www.acmicpc.net/problem/11724 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 import sys sys.setrecursionlimit(10 ** 6) # dfs 함수 정의 def dfs(start): visited[start] = True for i in graph[start]: if not visited[i]: dfs(i) # 정점의 개수 n , 간선의 개수 m n, m = map(int, sys.stdin.. 2023. 1. 14.
[백준/Python] 10026번: 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net import copy import sys sys.setrecursionlimit(10**6) n = int(input()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(sys.stdin.readline())) # copy 라이브러리를 통해 리스트 복사 graph2 = copy.deepcopy(graph) resu.. 2023. 1. 4.
[백준/Python] 1260번 : DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque import sys # 정점의 개수 , 간선의 개수 , 시작 정점 입력 받기 read = sys.stdin.readline n, m, v = map(int, read().split()) # 2차원 리스트 graph graph = [[] * n for _ in range(n + 1)] # 간선이 연결하는 두 .. 2022. 12. 29.
[백준 / Python] DFS_2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net # 컴퓨터의 수 from pprint import pprint n = int(input()) # 연결되어 있는 컴퓨터 쌍의 수 m = int(input()) graph = [[] * n for _ in range(n + 1)] # 리스트 생성 # [ [], # 1번노드 [2, 5], # 2번노드 [1, 3, 5], # 3번노드 [2], # 4번노드 [7], # 5번노드 [1, 2, 6], # 6번노드 .. 2022. 12. 29.
[BFS] 24445번 : 알고리즘 수업 - 너비 우선 탐색 2 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net from collections import deque import sys sys.setrecursionlimit(10 ** 9) input1 = sys.stdin.readline # 차례대로 정점의 수 , 간선의 수 , 시작 정점. n, m, r = map(int, input1().split()) graph = [[] for.. 2022. 12. 27.
[BFS] 백준 24444번 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 제출 코드 from collections import deque import sys sys.setrecursionlimit(10 ** 9) input1 = sys.stdin.readline # 차례대로 정점의 수 , 간선의 수 , 시작 정점. n, m, r = map(int, input1().split()) graph = .. 2022. 12. 27.

티스토리툴바