링크텍스트
백준 1260의 다양한 예제를 찾아보면 풀이가 굉장히 다양하다.
그렇게 때문에 처음 BFS를 시작했을 때 뭐야 쓔빨... 하면서 굉장히 당황했을 수 있을 것이다.
그래서 설명하는 알짜배기 강좌!
Bfs를 왜 쓸까?
탐색 알고리즘 중 하나이다.
출처 : 링크텍스트
사진에서 보듯이, 트리 또는 그래프에서 탐색을 할 때 bfs는 특정노드와 가까이 있는
즉 임의의 점을 기준으로 거리가 같은(ex 1.)애들을 먼저 탐색하고 이 후에는 거리가 2인 애들을 탐색하는 방법이 되겠다.
문제 유형
그리고 백준의 경우 문제가 2가지의 경우가 있는데
1. 트리형식
2. graph 형식
가 있다.
트리형식의 대표적인 예로 백준1260처럼, 예제가
이런식으로 어떤 임의의 정점간의 관계로 주어져있는 방법이 있다.
2번째로 graph 형식
유기농 배추
백준 1012번인 graph형식으로 주어져있는 게 있는데
보기만 해도 아찔해 보이는 입력처럼 나타나게 되는데
이건 트리처럼 그려지는게 아니라 x,y처럼 좌표처럼 보이게 된다는 것
하지만 이것도 트리처럼 생각할 수가 있는데
이렇게 생각이 가능하다는 것!
deque
deque라는 큐 자료구조가 있다.
Double-ended Queue의 약자로, 양쪽 끝의 삽입 삭제가 모두 가능한 자료구조 ! (큐와 스택을 합쳤다고 생각하면 됨!)
그래서 왜쓰냐!
앞뒤 요소를 넣고 빼야할 때 시간이 빨라서! 만 이해하면 된다.
list의 경우 시간복잡도가 pop(0)일때 O(n)이지만 deque는 다 O(1)이라는 것
deque를 왜 갑자기 설명하냐고요?
트리구조를 생각해 봅시다.
만약에 탐색을 해야한다고 생각해봅시다.
1부터 탐색을 하겠죠?
그런다음에 2,3,4순서로 탐색을 해야한다는 것은 알고있어
근데 컴퓨터는 그걸 어떻게 아냐고!
1260번의 예제 같은 경우에는 위에 올렸던 것처럼 1 2 처럼 노드 사이가 연결되어있음을 표시했지, 여기서 내가 배웠을 때 가장 헷갈렸던 점이 뭐냐면, 다른 모든 사람들의 풀이마다 이 연결되어 있다고 표시한 방법이 다른 경우가 많았다는거임!
즉, graph의 표시 방법이 다 달랐다는거
자 이 표시방법을 봅시다.
from collections import deque
n, m, v = map(int, input().split())
graph = [[0]*(n+1) for _ in range(n+1)]
# for i in range(m):
def dfs(v):
visited[v] = 1
print(v, end= " ")
for i in range(1, n+1):
if graph[v][i] == 1 and visited[i] == 0:
dfs(i)
for _ in range(m):
a, b = map(int, input().split())
graph[a][b] = graph[b][a] = 1
def bfs(v):
queue = [v]
visited_1[v] = 1
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in range(1, n+1):
if(graph[v][i] == 1 and visited_1[i]== 0):
queue.append(i)
visited_1[i] =1
visited= [0]*(n+1)
visited_1 = [0]*(n+1)
dfs(v)
print()
bfs(v)여기서의 그래프 표시방법은 graph[시작정점][도착정점] 이런식으로 2차원 행렬을 통해 구현되어 있다. 예를들자면 노드1과 노드 2가 연결되어 있다면 graph[1][2] == 1이라는 값이 참이 되겠지.
다른 경우를 봐보자
graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']이거는 결국 graph를 dict()로 선언해 각 노드에 연결되어 있는 노드들을 표시해논 것이다 1차원적 으로! 노드 이름이 A라서 저렇게 한거지, 만약 인덱스번호가 곧 노드 번호인 경우에는 dict를 사용하지 않아도 1차원적으로 선언할 수 있게 된다.
그렇기 때문에 우리는 graph 선언 방법(노드 사이의 연결관계를 어떻게 표현하는가)에 대해서 알아야 한다는 것임
구현
그러면 일단 우리는 그래도 알기 쉽게, 2차원으로 선언했다고 가정할게요. graph[1][2]라면, 노드1과 노드2사이의 연결관계라고 생각한다는 것
1260에서 봤듯이, 우리가 탐색을 하려면 2가지가 필요하다.
1. 탐색할 그래프, 2. 어디서부터 탐색할 지에 대한 시작점!
def bfs(graph, root):이렇게 일반적으로 인자를 graph, root를 두 개 주게되는데
편의상 1개의 graph를 탐색할 거기 때문에
def bfs(root):로 생각하겠다.2번째 고려사항
이제는 탐색을 할텐데, 내가 이미 탐색을 한 친구면 또 탐색을 하면 안된다. 그렇게 때문에! visited = []라는 배열을 선언을 해주는 거임, 그래서 방명록이라고 생각하면 된다!.
예를 들어 0번노드와 1번, 3번노드가 방문처리를 했을때
이런식으로 1로 처리가 되는거다.
동작원리
- 시작번호를 방문처리한다. + 방문했다고 출력
- 시작번호와 연결된 노드들을 방문처리한다.
- 연결된 노드의 또 연결된 노드들을 방문처리
- 연결된 노드의 또 연결된 노드들의 또 연결된 노드를 방문처리....
이렇게 이어지는데 핵심은
방문처리한 노드와 연결된 애들을 찾아서 넣으면 된다
라는것
이제 그걸 deque 구조에 넣을껀데,
왜 deque 구조에 넣는가?
먼저 시간이 단축이 된다, 위의 O(1)에서 설명했듯이.
while queue:
q = queue.popleft()while이란 반복문은 1,2,3,4의 과정을 반복하기 위해서 진행하는 것이다.
그에 따라 q라는 변수는 연결된 노드를 찾기 위한 시작점이 된다.
for i in range(1, n+1):
if(graph[q][i] == 1 and visited_1[i]== 0):
queue.append(i)
visited_1[i] =1이 후 왜 for문이 1부터 n+1인가?
-> 결국 연결된 노드의 개수는 정점의 개수인 1부터 n까지밖에 없다는 것이다.
1. graph[q][i] ==1 : q에서부터 1~n까지의 노드가 연결이 되어있다면
2. visited_1[i] == 0 : 그리고 그 노드가 방문이 안되어있는 노드라면
3. queue.append(i) : queue에 넣어준다. 왜? 그 노드와 연결되어 있는 노드를 찾아야 하기 때문에!
4. visited_1[i] == 1 : 그리고 방문처리
이렇게 구현을 하면 되겠다!
그리고나서 이건 트리형태의 경우 구현하는 방법이다.
트리형태의 경우 for i in range(1,n+1)을 통해 그 노드와 연결된 모든 노드를 찾았는데
앞서 미리 말했던 그래프형태의 경우
상하좌우를 확인해 줘야 한다.
근데 작성하기가 너무 힘듭니다... 다음에 시간이 나면 작성을 하겠습니다!
간단하게 말하자면, 그래프형태의 경우에는 상하좌우를 확인해 줘야한다.
내가 말하는 방법으로는 dx = [0,0,1,-1], dy = [1,-1,0,0,] 이렇게 두가지의 x,y 이동방법을 조합하게 된다면
임의의 x, y에 대해
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]의 코드의 x,y값은 총 4번의 값을 찾게 되는데
이렇게 총 상하좌우의 값을 찾게된다는 의미이다.
그리고 또 고려해야할 상황
위를 찾는데 리스트의 범위를 넘게되는 경우
그렇게 되면 list out of range에러가 뜨게 된다.
그 경우를 방지하기 위해서 nx, ny의 범위 행렬의 크기 안으로 조절해 주면 되는것이다.
여기서 더 나아가 조건을 추가해보자.
만약에 그래프 탐색을 상하좌우가 아닌 그 전방 범위 전체라면?
위의 dx = [0,0,1,-1], dy = [1,-1,0,0,]의 조합을 통해 총 상하좌우의 값을 만들었다. 그렇다면 8가지의 위치도 조합을 통해 만들 수 있지 않을까?
그거는 여러분에게 맡기겠습니다.
.
.
.
.
.
는 제가 해야죠!!!
이렇게 한다면 dx = [-1,-1,-1,0,0,1,1,1], dy = [-1,0,1,-1,1,-1,0,1]의 조합을 통해 모든 면을 관찰할 수가 있습니다.!! 여기까지....
혹시 한번이라도 보셨다면 댓글이나 따봉좀 해주세요... 힘이납니다.
