by
Oct 16. 2020
Python BFS
백준 문제 풀이 (2606)
백준 문제를 통해 BFS에 대해 알아보자
BFS는 너비우선탐색(Breadth-First Search)의 약자이다. 문제를 풀면서 이해하는 것이 빠르므로 아래 문제를 풀어보면서 공부해보자.
BFS를 공부하기 위해 풀어볼 문제는 2606번 문제이다.
https://www.acmicpc.net/problem/2606
컴퓨터를 숫자로 표현하고 이렇게 연결되어 있다고 가정하자. 취약점에 의해 1번 컴퓨터가 악성코드에 감염되었는데 이 악성코드가 전파능력이 있다면 추가적으로 2,5,6,3번 컴퓨터가 감염될 것이다.
그럼 1번 컴퓨터에 의해 감염될 수 있는 컴퓨터 개수는 4대이다.
위처럼 컴퓨터를 노드라고 할 때 노드와 노드의 관계를 간선으로 표현할 수 있고 그림으로 도식화한 것을 그래프라고 한다.
BFS는 이런 그래프에서 관계를 모두 두 다 조회해야할 경우 필요하다. 보통 프로그래밍 테스트 고급에서 자주 사용된다. 사실 BFS만 사용하는 것은 아무런 의미가 없다. 여기에 메모이제이션 기법이 들어가야 진짜 의미있는 탐색이 되지만 메모이제이션 기법은 추후 알아보고 우선 BFS를 통해 모든 노드를 조회하는 코드를 작성해보자
이런 관계를 표현하는 방법은 배열 또는 리스트를 이용할 수 있다.
배열을 통해 표현하는 방법은 다음과 같다.
Arr[0][0] ~ Arr[7][7] 까지 모두 특정 값으로 초기화 해놓고
1번과 2번이 연결되어있다면
Arr[1][2] = 표시
Arr[2][1] = 표시
하는 방법이다.
지금은 방향성이 없으므로 모두 표시했고 만약 1번에서 2번으로만 이동할 수 있는 경우엔 Arr[1][2]에만 표시를 한다.
lines[1] = [0, 1, 0, 0, 1, 0, 0]
lines[2] = [1, 0, 1, 0, 1, 0, 0]
lines[3] = [0, 1, 0, 0, 0, 0, 0]
...
이처럼 모둔 배열을 0으로 초기화 해놓고 연결될 경우 1로 다시 표시해놓는 방법을 사용한다.
배열을 이용해 간선을 표현하는 방법은 노드의 개수가 작을 때는 가볍게 구현할 수 있지만 노드의 개수가 많아진다면 모두 조회해야해서 매우 느려지는 단점이 있다. 하지만 간단하므로 효율적으로 메모리를 관리할 수 있다. 소스코드는 다음과 같다.
리스트를 이용한 방법은 다음과 같이 연결된 경우에만 노드번호를 가지고 있는 것이다.
Arr[1] = [2, 5]
Arr[2] = [1, 3, 5]
Arr[3] = [2]
Arr[4] = [7]
Arr[5] = [1, 2, 6]
Arr[6] = [5]
Arr[7] = [4]
소스코드는 다음과 같다.
2가지 방법을 모두 이용해서 소스코드를 구현해보자.
BFS는 큐를 이용하는데 다음에 탐색할 노드를 큐에 넣은 뒤 노드를 방문할 때마다 큐에서 뺀 다음 연결된 모든 간선을 조회한다.
코드는 queue에다가 값을 저장하며 하나씩 뺀 뒤 연결된 모든 노드를 다시 큐에 넣는 방법으로 조회한다. 방문하지 않은 노드는 visit 배열에 표시해놓고 방문한 노드는 다시 조회할 필요 없으므로 패스한다.
배열을 이용해 조회하는 방법은 다음과 같다. for문을 유심히 보자
리스트를 이용해서 조회하는 방법은 다음과 같다.
이후 visit 배열에 표시해놓은 것을 참고하여 카운트를 계산한다.
