본문 바로가기
반응형

알고리즘/그래프 탐색12

[백준][Python] 14502번 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 코드 from collections import deque import copy def bfs(): queue = deque() c_graph = copy.deepcopy(graph) for i in range(n): for j in range(m): if c_graph[i][j] == 2: queue.append((i,j)) while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] .. 2022. 11. 9.
[백준][Python] 1697번 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 코드 from collections import deque def dfs(): queue = deque() queue.append(n) while queue: nx = queue.popleft() if nx == k: return visit[nx] for i in (nx-1,nx+1,nx*2): if 0 2022. 10. 26.
[백준][Python] 4963번 섬의 개수 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 코드 import sys from collections import deque def bfs(x,y): dx = [-1,-1,-1,0,0,1,1,1] dy = [-1,0,1,-1,1,-1,0,1] queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0 2022. 10. 7.
[백준][Python] 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 코드 def bfs(i): queue = [] queue.append(i) while queue: num = queue.pop() for a in graph[num]: if visit[a] == 0: visit[a] = 1 queue.append(a) n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): u,.. 2022. 10. 6.
반응형

티스토리툴바