Problem Solving/DFS, BFS26 [DFS, BFS] 백준 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net import copy import sys x_lim, y_lim = map(int, input().split()) table = [] virus = [] empty = [] for i in range(x_lim): table.append(list(map(int, input().split()))) for j in range(y_lim): if table[i][j] == 2: virus.append([i, j]).. 2021. 5. 29. [DFS, BFS] 백준 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 collections n, m = map(int, input().split()) graph = collections.defaultdict(list) for i in range(m): u,v = map(int, input().split()) graph[u].append(v) graph[v].append(u) discovere.. 2021. 5. 29. [DFS, BFS] 백준 1697번: 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net import collections n, k = map(int, input().split()) q = collections.deque() q.append(n) discovered = [n] count = 0 while q: for i in range(len(q)): cur = q.popleft() if cur == k: print(count) quit() next = [c.. 2021. 5. 29. [DFS, BFS] 백준 7576번: 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 으아아아악!!! 중간에 꼬여서 3시간 정도 걸린 거 같다.. import collections y_lim, x_lim = map(int, input().split()) table=[] for i in range(x_lim): table.append(input().split()) q = collections.deque() for x in range(x_lim): for y in ra.. 2021. 5. 24. [DFS, BFS] 백준 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import collections n = int(input()) link = int(input()) table = collections.defaultdict(list) for i in range(link): a, b = map(int, input().split()) table[a].append(b) table[b].append(a) discovered=[] def dfs(computer): for ot.. 2021. 5. 24. [DFS, BFS] 백준 2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 섬을 세는 유명한 문제에 갯수까지 세는 것이 추가된 문제다. DFS로 탐색하면서 미지의 단지를 발견할때 마다 island에 1을 더해주고 ( 단지 개수) 집을 발견할때마다 1을 더해주는 식으로 단지 내 집 개수를 구하였다. n = int(input()) table = [] for i in range(n): table.append(list(input())) island = 0 houses = [] d.. 2021. 5. 24. 이전 1 2 3 4 5 다음
