Algorithm_PYTHON24 [백준_파이썬]2178번_미로탐색 # 최소의 칸 수 = 최소 이동거리 => bfs from collections import deque queue = deque() # 방향설정 dx = [1, -1, 0, 0] dy = dx[::-1] n, m = map(int, input().split()) def bfs(x, y): queue.append((x,y)) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] # 범위 안에 있고, if 0 2021. 8. 23. [백준_파이썬]2606번_바이러스 내 풀이 - BFS 바이러스라서 뭔가 사방으로 퍼져나간다고 생각하여 BFS로 풀어봄 from collections import deque queue = deque() # deque를 사용하기 위한 선언 coms = int(input()) # 컴퓨터 수 connect = int(input()) # 연결된 쌍 graph = [[] for _ in range(coms+1)] # 인덱스 0번째 안쓸 거니까 +1해줌 # graph 정보 입력 for _ in range(connect): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x) visited = [False] * (coms+1) # 노드갯수 + 1(인덱스 0안쓸거니까) def bf.. 2021. 8. 22. [백준_파이썬]1260번_DFS와 BFS 풀이 1 from collections import deque N, M, V = map(int, input().split()) graph = [[] for _ in range(N+1)] # 1부터 시작하니까 인덱스 0버릴 생각 visited = [False] * (N+1) # 인덱스 0은 안쓸 생각 for _ in range(M): a, b = map(int, input().split()) # 연결된 노드들 전부 표시 위함 graph[a].append(b) graph[b].append(a) for i in graph: i.sort() def dfs(graph, v, visited): # 현재 노드 방문 처리 visited[v] = True print(v, end=" ") # 해당 노드와 연결되어 있는 노.. 2021. 8. 22. [알고리즘] CH05 탐색 알고리즘 DFS, BFS ※ 모든 경로 탐색시엔 DFS/BFS 둘 다 사용 가능 BUT, 최단 거리 문제는 BFS가 더 효과적 단, 모든 간선의 비용이 동일할 때만! 만약, 간선의 비용이 다르다면 다익스트라 사용 그래프 : 노드(=정점: Vertex)와 간선(Edge)으로 표현 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 - 두 노드가 간선으로 연결되어 있다 => '두 노드는 인접하다'고 표현 - 노드는 도시, 간선은 도시들을 연결하는 도로라고 생각 그래프의 2가지 표현방법 1. 인접 행렬(Adjacency Metrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 - 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 - 연결된 그래프를 인접 행렬로 표현할 때, 2차원 리스트로 구현 가능 - 연결.. 2021. 8. 22. 이전 1 2 3 4 5 6 다음