본문 바로가기

분류 전체보기85

[백준/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.
BFS_미로탈출 이코테 from collections import deque n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이동할 네 방향 정의(상,하,좌,우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS 소스코드 구현 def bfs(x, y): # 큐 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append((x, y)) # 큐가 빌 때까지 반복 while queue: x, y = queue.popleft() # 현재 위치에서 네 방향으로의 위치 확인 for i in range(4): .. 2022. 12. 27.
DFS_ 음료수 얼려 먹기 이코테 n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # DFS 깊이 우선 탐색을 통해 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문 def dfs(x, y): # dfs 함수 정의 # 주어진 범위를 벗어나는 경우에는 즉시종료 if x = n or y = m: return False # 현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: # 해당 노드를 방문 처리 graph[x][y] = 1 # 상,하,좌,우의 위치도 모두 재귀적으로 호출 dfs(x - 1, y) # 상 dfs(x, y - 1) # 좌 dfs(x .. 2022. 12. 27.

티스토리툴바