목록BOJ_백준/DFS_BFS (4)
haju__log
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys from collections import deque def bfs(i,j,rain): queue=deque() visited[i][j]=1 queue.append((i,j)) #상하좌우 계산 dx=[0,0,1,-1] dy=[1,-1,0,0] while queue: x,y=queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] #범위안에 ..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ✅ 첫 번째 시도 import sys def dfs(x,y): #상하좌우를 살피기 위함 dx=[0,0,-1,1] dy=[1,-1,0,0] for i in range(4): nx=x+dx[i] ny=y+dy[i] if (0
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net ✅ 문제풀이 다른 부분에선 막히는 게 없었는데 dfs를 수행하여 방문처리하는 노드의 수를 어떻게 셀 것인가에 대해 고민을 꽤 했다. global 전역변수를 사용하여 그 문제를 쉽게 해결할 수 있었다. import sys result=0 def dfs(v): #result를 전역변수로 사용함 (global 사용하여) global result visited[v]=1 result += 1 for i in r..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import sys #dfs 함수 def dfs(v): #v를 방문처리해서 True로 저장한다. visited[v]=True #방문처리한 노드는 출력 print(v,end=' ') #반복문을 돌면서 1번 노드와 인접한 노드들이 있는지 확인한다. for i in range(1,n+1): #만약 인접한 노드가 있고, 아직 방문하지 않았다면 (false는 방문처리 ..