BFS
BFS를 그래프 문제를 풀면서 이해해보자!
그래프
그래프에서 이용되는 BFS
BFS는 너비우선탐색으로, 가까운 노드들부터 탐색하면서 길을 헤쳐나간다.
1이 시작노드면, 2,3 탐색하고 / 다음 2와 가까운 4,5 탐색 <- 이런식으로 진행된다.
** 주의할점 - 방문했던 노드를 또 다시 방문하는 건 비효율적이고, 무한루프가 될 가능성이 있으므로 방문했던 노드는 체크표시를 하면서 진행한다.
BFS 그림으로 알아보기
- 시작할 노드를 체크하면서 큐에 넣음 -> 1번 빼내면서 1에 인접한 노드 2,3번 체크표시 -> 2번과 3번 큐에 넣음
- 2번 빼내면서 2번에 인접한 3,4,5 체크표시 -> 3,4,5 큐에 넣음(1도 인접하지만 1은 체크표시가 되어 있기 때문에 큐에 넣지 않음)
- 3번 빼내면서 3번에 인접한 7,8 큐에 넣음(1,5도 인접하지만 체크표시여서 큐에 넣지 않음) -> 7,8, 체크표시
- 계속 반복
-> 노드 방문 순서 1,2,3,4,5,7,8,6
BFS 수도코드로 알아보기
- 출발점 s에서 시작(큐에 넣음) -> visited도 체크해야하면 체크
- 큐가 비어있지 않은동안 반복문 돌림
- 큐에서 노드 하나를 꺼냄
- 그 노드에 인접한 노드들을 for문 돌리고, 방문되지 않았다면 방문하고 queue에 넣음
- 큐가 빌 때까지 반복
BFS 실제 파이썬 코드로 알아보기
- 문제
-> 그래프의 인접 행렬을 보고 그곳으로 가는 경로가 있는지 없는지 행렬 형식으로 나타내면 된다.
인접 행렬이 뭐지?
인접행렬 : 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬
-> 간단히 말해서, 모든 배열이 0으로 초기화 되어 있고 갈 수 있는 정점에 한해서는 1로 표시되어 있는 행렬이다.
ex) 2가 갈 수 있는 정점은 3뿐이니, 3에만 1이 적혀있다. / 1이 갈 수 있는 정점은 2,3,4여서 2,3,4에 1이 적힘
다시 문제로 돌아옴
- 입력 예시
-> 즉, 밑의 그림처럼 나타낼 수 있다.
- 출력 예시
-> 각 정점에 어떤 방법을 써서든 도달할 수 있으면 1, 도달할 수 없으면 0을 출력한다.
ex) 0에서 0으로 가는 방법 : 있음 (1) / 0에서 2로 가는 방법 : 있음 (1)
문제를 이해했으니 실제로 풀어보자!
-
입력받기
N = int(input()) arr=[list(map(int,input().split())) for _ in range(N)]
-
bfs를 돌아서, 만약 길을 다 돌았는데 길이 없으면 print(0), 중간에 길을 찾으면 print(1)하고 return하는 함수를 호출
for i in range(N): for j in range(N): bfs(i, j) print()
-
위에서 말한 함수 정의
-
함수는 BFS를 사용하므로, 아까 위에서 배웠던 bfs를 가져온다!
# 1. Queue 만들어줌 deq = deque() # 2. 방문했는지 체크여부 만들어줌 visited = [0 for i in range(N)] # 3. 큐에 첫 번째 값 넣음 deq.append(start) # 4. while 문을 돌린다(큐가 없어질 때까지 계속 실행) while len(deq)!=0: # 5. 큐에서 노드 꺼내기 current = deq.popleft() # 6. 인접한 노드 찾음 for i in range(N): # 7. 간선이 연결되어 있고(인접한 노드이고), 방문을 하지 않은 곳이라면? if(arr[current][i]==1 and visited[i]==0): # 8. 방문 됐다고 표시 visited[i] = 1 # 9. 그 노드를 큐에 넣음 deq.append(i)-> 이게 수도코드를 변환한 코드이다.
-
여기서 우리는 길이 있다면 print(1)을 찍고, 없다면 print(0)을 찍어야 한다.
-> 위의 코드를 조금만 변형하면 할 수 있다
-> 우리는 bfs인자로 start, end를 줬었다.
=> 만약 0에서 2로 갈 수 있는지 없는지를 탐색하기 원한다면 bfs(0,2)로 함수가 들어오는 것이다.그럼 인접한 노드의 반복문을 돌릴 때 그 중에서 2가 있다면? print(1)을 해주면 된다
# 7번 코드를 가져온다. if(arr[current][i]==1 and visited[i]==0): # 인접한 노드 중에서 방문을 하지 않은 곳이라면? if(i==end): # 인접한 노드와 2가 일치한다면, print(1)을 해주고 return 한다. print(1, end=" ") return-> 그리고, while문이 다 끝난 후에도 return이 안 됐다면 print(0)을 찍어주면 끝
이해가 안 된다면? 그림으로!
0에서 2로 갈 수 있는 길이 있는지 없는지 궁금하다.
0에서 2로 갈 수 있는 길을 알고싶으면 우리가 만든 bfs 함수에 인자로 (0,2)를 넣어주게 될 것이다.
=> bfs(0,2) 이런식!
그럼, 간선을 따라 방문하는 반복문 코드에서 2가 나타난다면! print(1)을 해주면 된다
-> 간선을 따라 방문하는 반복문 코드는 어떤 식으로 이루어져 있지?
- 0의 근처 노드들을 탐색한다 -> 간선이 있고, 방문 안 한 코드 뭐가 있지? -> 1
- 1의 근처 노드들을 탐색한다 -> 간선이 있고, 방문 안 한 코드 뭐가 있지? -> 2
=> 반복문 도는데 2가 나왔다! 2로 갈 수 있는 길이 있네! -> print(1) / return
최종 코드
from collections import deque
N = int(input())
arr=[list(map(int,input().split())) for _ in range(N)]
def bfs(start,end):
deq = deque()
visited = [0 for i in range(N)]
deq.append(start)
while len(deq)!=0:
current = deq.popleft()
for i in range(N):
if(arr[current][i]==1 and visited[i]==0):
if(i == end):
print(1, end=" ")
return
visited[i] = 1
deq.append(i)
print(0, end=" ")
for i in range(N):
for j in range(N):
bfs(i, j)
print()
