BFS(Breadth First Search, 너비 우선 탐색)
시작 노드의 인접한 노드를 모두 방문한 후, 방문했던 노드의 인접한 노드를 방문하는 것을 반복한다.
큐를 사용해 구현할 수 있다.
큐에 한 번 들어가게 되면 방문이 확정된다. 따라서 큐에 들어가는 노드는 다시 큐에 들어갈 필요가 없으므로 visited를 사용해 방문 표시하고 방문에서 제외한다. 방문시 값을 변경해도 되는 것은 따로 visited를 만들지 않고 연관 없는 숫자로 바꾸어 방문을 표시해도 된다.
풀이 바로가기
<배열로 이루어진 문제>
<노드와 간선으로 이루어진 문제>
1926번 그림
from collections import deque
n,m=map(int, input().split())
graph=[list(map(int, input().split())) for _ in range(n)]
visited=[[False] * m for _ in range(n)] # 그래프 크기만큼 방문여부 리스트를 만든다
cnt=0 # 그림의 개수
big_p=0 # 제일 큰 그림의 크기
# [상,하,좌,우]
dx=[-1,1,0,0] # 상하이동
dy=[0,0,-1,1] # 좌우이동
def bfs(x,y):
q=deque()
q.append((x,y))
p_max=1 # 그림 크기 1
visited[x][y]=True
while q:
x,y=q.popleft()
for i in range(4): # 상하좌우 이동하면서
nx=x+dx[i] # 상하이동
ny=y+dy[i] # 좌우 이동
if 0<=nx<n and 0<=ny<m:
if graph[nx][ny]==1 and visited[nx][ny]==False: #1이면서 아직 방문을 안했으면
p_max+=1 # 그림 크기 증가
visited[nx][ny]=True # 방문했음으로 바꾼다
q.append((nx,ny)) # 큐에 다음 위치 추가
return p_max
for i in range(n):
for j in range(m):
if graph[i][j]==1 and visited[i][j]==False: # 값이 1이면서 방문x
cnt+=1 # 그림 개수 증가
result=bfs(i,j)
if big_p<result: # 탐색하면서 그림 크기 구하기
big_p=result
print(cnt)
print(big_p)
2178번 미로 탐색
가중치가 없는 그래프에서는 BFS를 이용해 최단 경로를 구할 수 있다.
# graph[0][0]에서 출발해 graph[n-1][m-1]에 도착하는 최단 경로를 구하는 문제(가중치가 없다)
# bfs로 1이 있는 곳을 방문하면서 거리를 구한다.
# 방문한 곳에 직접 거리를 표시해 방문체크가 따로 필요하지 않다.
from collections import deque
n,m=map(int, input().split())
graph=[list(map(int, input())) for _ in range(n)]
# [상,하,좌,우]
dx=[-1,1,0,0] # 상하이동
dy=[0,0,-1,1] # 좌우이동
def bfs(x,y):
q=deque()
q.append((x,y))
while q:
x,y=q.popleft()
for i in range(4): # 상하좌우 이동하면서
nx=x+dx[i] # 상하이동
ny=y+dy[i] # 좌우 이동
if 0<=nx<n and 0<=ny<m: # 미로를 벗어나지 않는다.
if graph[nx][ny]==1: # 아직 방문하지 않은 길이면
graph[nx][ny]=graph[x][y]+1
q.append((nx,ny)) # 큐에 다음 위치 추가
return graph[n-1][m-1]
print(bfs(0,0))
2667번 단지번호붙이기
from collections import deque
n=int(input())
graph=[list(map(int, input())) for _ in range(n)]
cnt=0 # 단지수
cnt_arry=[] # 단지에 속하는 집의 수
# [상,하,좌,우]
dx=[-1,1,0,0] # 상하이동
dy=[0,0,-1,1] # 좌우이동
def bfs(x,y):
q=deque()
q.append((x,y))
graph[x][y]=2
cnt_house=1
while q:
x,y=q.popleft()
for i in range(4): # 상하좌우 이동하면서
nx=x+dx[i] # 상하이동
ny=y+dy[i] # 좌우 이동
if 0<=nx<n and 0<=ny<n: # 미로를 벗어나지 않는다.
if graph[nx][ny]==1: # 아직 방문하지 않은 길이면
graph[nx][ny]=2 # 숫자를 바꾼다
cnt_house+=1 # 집의 개수를 증가
q.append((nx,ny)) # 큐에 다음 위치 추가
return cnt_house
for i in range(n):
for j in range(n):
if graph[i][j]==1:
cnt+=1 # 단지수 증가
cnt_arry.append(bfs(i,j))
print(cnt)
cnt_arry.sort() # 오름차순 정렬
for i in range(cnt):
print(cnt_arry[i])
7576번 토마토
# 토마토가 있는 위치에서 동시에 주변으로 탐색하는게 포인트
# 처음에 토마토가 있는 위치를 모두 큐에 삽입하고 bfs에서 꺼낸다
from collections import deque
m,n=map(int, input().split())
graph=[list(map(int, input().split())) for _ in range(n)]
q=deque()
# [상,하,좌,우]
dx=[-1,1,0,0] # 상하이동
dy=[0,0,-1,1] # 좌우이동
def bfs():
while q:
x,y=q.popleft()
for i in range(4): # 상하좌우 이동하면서
nx=x+dx[i] # 상하이동
ny=y+dy[i] # 좌우 이동
if 0<=nx<n and 0<=ny<m: # 상자를 벗어나지 않는다.
if graph[nx][ny]==-1: # 비어있는 자리라면
continue # 넘긴다
if graph[nx][ny]==0: # 토마토가 있으면
graph[nx][ny]=graph[x][y]+1 # 전값에 +1을 한다
q.append((nx,ny)) # 큐에 다음 위치 추가
for i in range(n): # 행
for j in range(m): # 열
if graph[i][j]==1:
q.append((i,j))
bfs()
f=1 # 토마토가 익었는지 안익었는지 확인
# 그래프의 원소값을 하나씩
for i in graph:
for j in i:
if j==0:# 토마토가 다 익지 않았으면
f=0
break
if f==0:
print(-1)
else:
print(max(map(max, graph))-1) # 2차원 리스트에서 최대값 찾기
7569번 토마토
원래 토마토 문제가 2차원 배열이었다면 이 문제는 위로 상자가 쌓이면서 3차원 배열이 되었다.
# 토마토가 있는 위치에서 동시에 주변으로 탐색하는게 포인트
# 처음에 토마토가 있는 위치를 모두 큐에 삽입하고 bfs에서 꺼낸다
# 3차원 배열
from collections import deque
m,n,h=map(int, input().split())
graph=[[list(map(int, input().split())) for _ in range(n)] for _ in range(h)] # 3차원 배열 입력받기
q=deque()
cnt=0
# [상,하,좌,우, 아래,위]
dx=[-1,1,0,0,0,0] # 상하이동
dy=[0,0,-1,1,0,0] # 좌우이동
dz=[0,0,0,0,-1,1] # 위아래이동
def bfs():
while q:
x,y,z=q.popleft()
for i in range(6): # 상하좌우위아래 이동하면서
nx=x+dx[i] # 상하이동
ny=y+dy[i] # 좌우 이동
nz=z+dz[i] # 위아래 이동
if 0<=nx<n and 0<=ny<m and 0<=nz<h: # 상자를 벗어나지 않는다.
if graph[nz][nx][ny]==-1: # 비어있는 자리라면
continue # 넘긴다
if graph[nz][nx][ny]==0: # 토마토가 있으면
graph[nz][nx][ny]=graph[z][x][y]+1 # 전값에 +1을 한다
q.append((nx,ny,nz)) # 큐에 다음 위치 추가
for k in range(h): # 높이
for i in range(n): # 행
for j in range(m): # 열
# 높이
if graph[k][i][j]==1:
q.append((i,j,k))
bfs()
f=1 # 토마토가 익었는지 안익었는지 확인
# 그래프의 원소값을 하나씩
for i in graph:
for j in i:
for k in j:
if k==0:# 토마토가 다 익지 않았으면
f=0
break
cnt=(max(cnt,max(j))) # 1차원 배열에서 맥스값 찾고 다시 맥스값 찾기
if f==0:
print(-1)
else:
print(cnt-1)
2206번 벽 부수고 이동하기
from collections import deque
n,m=map(int, input().split())
graph=[list(map(int, input())) for _ in range(n)]
# 0: 이동가능 , 1: 벽
# 벽을 한개까지 부술 수 있다
dx=[-1,1,0,0]
dy=[0,0,-1,1]
# 3차원 리스트(행,열,벽)
visited=[[[0]*2 for _ in range(m)] for _ in range(n)]
visited[0][0][0]=1
# [][][0]-> 벽을 부순적이 없다
# [][][1]-> 벽을 이미 한 번 부쉈다
def bfs(x,y,z):
q=deque()
q.append((x,y,z))
while q:
x,y,z=q.popleft()
if x==n-1 and y==m-1: # 목적지에 도착했으면
return visited[x][y][z]
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<m:
if graph[nx][ny]==0 and visited[nx][ny][z]==0: # 이동 가능하고 한번도 방문하지 않음
visited[nx][ny][z]=visited[x][y][z]+1 # 전의 값에 +1
q.append((nx,ny,z)) # 다음 값을 넘기면서 벽의 상태 유지
# z==0일때 벽을 부수면 z=1이 되므로 z==0의 조건을 만족하는 경우가 생기지 않음(한번만 부숴진다)
elif graph[nx][ny]==1 and z==0: # 벽이면서 아직 벽을 부순적이 없음
visited[nx][ny][1] = visited[x][y][0] + 1 # [][][1]에 전 값을 저장하여 앞으로는 벽을 부순 상태에 계속 저장힘
q.append((nx, ny, 1)) # 다음 값을 넘기면서 벽의 상태 변경
return -1
print(bfs(0,0,0))
10026번 적록색약
# 색약이 아닐 때의 구역을 구한다
# 적록색을 하나의 색으로 표현한다
# 적록색약일 때의 구역을 구한다
from collections import deque
n=int(input())
graph=[list(input()) for _ in range(n)]
normal=0 # 일반
rg=0 # 적록색약
visited=[[0]*n for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs(x,y):
q=deque()
q.append((x,y))
visited[x][y]=1 # 방문 표시
while q:
x,y=q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n: # 범위 내
if graph[nx][ny]==graph[x][y] and visited[nx][ny]==0: # 색깔이 같으면서 방문한 적이 없을때
visited[nx][ny]=1 # 방문 표시
q.append((nx,ny))
# 색약이 아닐 때
for i in range(n):
for j in range(n):
if visited[i][j]==0:
bfs(i,j)
normal+=1
# 색약일 때
visited=[[0]*n for _ in range(n)] # 방문기록 초기화
for i in range(n):
for j in range(n):
if graph[i][j]=='G': # 적록색을 하나의 색으로 표시
graph[i][j]='R'
for i in range(n):
for j in range(n):
if visited[i][j]==0:
bfs(i,j)
rg+=1
print(normal, rg)
2468번 안전 영역
from collections import deque
n=int(input())
graph=[list(map(int, input().split())) for _ in range(n)]
result=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs(x,y):
q=deque()
q.append((x,y))
visited[x][y]=1 # 방문 표시
while q:
x,y=q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n: # 범위 내
if new_map[nx][ny]==0 and visited[nx][ny]==0: # 잠기지 않았으면서 방문한 적이 없을때
visited[nx][ny]=1 # 방문 표시
q.append((nx,ny))
# 가장 높은 높이를 찾는다
# 반복문으로 0~높은 높이 반복하면서
# 현재 높이보다 작은 위치는 0으로 만든다
# 탐색 bfs로 구역의 개수를 계산한다
max_h=0
for i in graph:
max_h=max(max_h,max(i)) # 가장 높은 높이
for h in range(max_h+1): # 제일 높은 값은 어차피 다 잠겨서 구역이 0이되므로 제외해도 된다
# 높이가 바뀌면 리셋
new_map=[[0]*n for _ in range(n)]
visited=[[0]*n for _ in range(n)]
cnt=0
# 새로운 맵 만들기
for i in range(n):
for j in range(n):
if graph[i][j]<=h: # 현재 높이보다 작으면
new_map[i][j]=1 # 잠긴부분은 1로 처리(0을 센다)
# 새로만든 맵으로 탐색
for i in range(n):
for j in range(n):
if new_map[i][j]==0 and visited[i][j]==0: # 잠기지 않고, 방문하지 않았으면
cnt+=1
bfs(i,j)
result.append(cnt)
print(max(result))
11724번 연결 요소의 개수
from collections import deque
import sys
input=sys.stdin.readline # 이 문제에서 없으면 시간초과가 일어난다
n,m=map(int, input().split())
graph=[[0]*(n+1) for _ in range(n+1)]
visited=[0]*(n+1)
for i in range(m):
x,y=map(int,input().split())
graph[x][y]=graph[y][x]=1
def bfs(v):
q=deque()
q.append(v)
visited[v]=1
while q:
v=q.popleft()
for i in range(1,n+1):
if graph[v][i]==1 and visited[i]==0:
q.append(i)
visited[i]=1
cnt=0
for i in range(1,n+1):
if visited[i]==0:
bfs(i)
cnt+=1
print(cnt)
1389번 케빈 베이컨의 6단계 법칙
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int, input().split())
graph=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
x,y=map(int,input().split())
graph[x][y]=graph[y][x]=1
def bfs(v):
q=deque()
q.append(v)
num=[0]*(n+1)
visited[v]=1
while q:
v=q.popleft()
for i in range(1,n+1):
if graph[v][i]==1 and visited[i]==0:
q.append(i)
visited[i]=1
num[i]=num[v]+1 # 전 단계 수에 +1
return sum(num) # 각 번호의 사람을 만나기까지 걸린 단계의 합
cnt=[]
for i in range(1,n+1):
visited=[0]*(n+1)
cnt.append(bfs(i))
print(cnt.index(min(cnt))+1)
11725번 트리의 부모 찾기
from collections import deque
import sys
input=sys.stdin.readline
n=int(input())
# graph=[[0]*(n+1) for _ in range(n+1)]
graph=[[] for _ in range(n+1)] # 연결상태만 표시하는 방식으로 변경
parents_node=[0]*(n+1) # 부모노드가 무엇인지 저장
visited=[0]*(n+1)
for _ in range(n-1):
x,y=map(int,input().split())
# 그동안 2차원 배열로 문제를 풀었는데 메모리 초과가 뜨는 경우가 발생했다.
# graph[x][y]=graph[y][x]=1
graph[x].append(y)
graph[y].append(x)
# [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]] 저장이 이런식으로 된다
def bfs(v):
q=deque()
q.append(v)
visited[v]=1
while q:
v=q.popleft()
for i in graph[v]: # 현재 노드와 연결된 노드들을 확인한다
if visited[i]==0: # 방문하지 않았으면
q.append(i)
visited[i]=1
parents_node[i]=v # 다음에 탐색할 노드의 부모노드는 현재노드다
bfs(1)
for i in range(2,n+1):
print(parents_node[i])
1707번 이분 그래프
from collections import deque
import sys
input=sys.stdin.readline
def bfs(v):
q=deque()
q.append(v)
visited[v]=1 # 정점을 두 분류로 나누기 위해 1 or -1로 구분한다
while q:
v=q.popleft()
for i in graph[v]: # 현재 노드와 연결된 노드들을 확인한다
if visited[i]==0: # 방문하지 않았으면
q.append(i)
visited[i]=-visited[v] # 현재 노드에 인접한 노드는 다른 분류로 나눈다
elif visited[i]==visited[v]: # 인접한 노드와 현재노드의 분류가 같다면
return False
return True
k=int(input()) # 테스트 케이스
for _ in range(k):
v,e = map(int, input().split()) # 정점과 간선의 개수
graph=[[] for _ in range(v+1)] # 연결상태만 표시하는 방식으로 변경
visited=[0]*(v+1)
for _ in range(e):
x,y=map(int,input().split())
graph[x].append(y)
graph[y].append(x)
for i in range(1,v+1):
if visited[i]==0:
result=bfs(i)
if result==False:
break
print('YES' if result==True else 'NO') # 대문자로 출력..
1939번 중량제한
from collections import deque
import sys
input=sys.stdin.readline
def bfs(a,b,c):
q=deque()
q.append(a)
visited[a]=1
while q:
a=q.popleft()
if b==a:
return True
for i,w in graph[a]: # 현재 노드와 연결된 노드들을 확인한다
if visited[i]==0 and w>=c: # 방문하지 않았으면서 무게제한 통과
q.append(i)
visited[i]=1
return False # 가능한 모든 섬을 방문했는데 시작과 끝 섬이 연결되지 않으면 false
n,m = map(int, input().split()) # 정점과 간선의 개수
graph=[[] for _ in range(n+1)] # 연결상태만 표시하는 방식으로 변경
for _ in range(m):
x,y,c=map(int,input().split())
graph[x].append((y,c))
graph[y].append((x,c))
a,b=map(int, input().split()) # 공장이 위치한 두 섬
# 이분 탐색
# 중량제한 값을 보내 경로가 성립하는지 확인한다.
# 성립은 끝 섬의 방문여부가 1인지 확인한다.
s ,e = 1, 1000000000
result=s
while s<=e:
visited=[0]*(n+1)
mid=(s+e)//2
if bfs(a,b,mid): # mid 중량제한. 참일경우
result=mid
s=mid+1 # 중량제한을 통과했어도 더 큰값이 있을 수 있으니 확인
else:
e=mid-1 # 중량제한을 통과하지 못하면 작은값으로 다시 확인
print(result)'알고리즘' 카테고리의 다른 글
| N과 M 시리즈-백트래킹 (0) | 2022.06.26 |
|---|---|
| 백준 DFS 모음 (0) | 2022.06.24 |
| [백준 알고리즘] 1010번 다리 놓기. 파이썬(python) (0) | 2022.06.13 |
| [백준 알고리즘] 가장 긴 증가하는 부분수열1~4. 파이썬(python) (0) | 2022.06.13 |
| [백준 알고리즘] 9095번 1, 2, 3 더하기. 파이썬(python) (0) | 2022.06.04 |