BFS
BFS&DFS_심화21) 인구이동 _ python
문제링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 코드 # 인구이동 - bfs from collections import deque n, l , r = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(x, y)..
BFS&DFS_심화17) 경쟁적 전염 _ python
문제링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 코드 # 경쟁적 전염 - bfs from collections import deque N, K = map(int, input().split()) graph = [] virus = [] for i in range(N): graph.append(list(map(int, input().split()))) for j in range(N): if graph[i][j]..
BFS&DFS_심화16) 연구소 _ python
문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 코드 from itertools import combinations from collections import deque import copy n, m = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) virus = [] # 바이러스의 좌표 empty = [] # ..
BFS&DFS_심화15) 특정 거리의 도시 찾기 _ python
문제 링크 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 코드 # https://www.acmicpc.net/problem/18352 from collections import deque import sys f = sys.stdin.readline n, m, k, x = map(int, f().split()) graph = [[] for _ in range(n+1)] d..
3주차 - DFS/BFS
그래프 탐색 알고리즘 : DFS / BFS 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 스택(Stack) 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출..