[python] BFS 문제 풀기

python 으로 BFS 문제 풀기

우선 코드부터 보고 아래에 설명을 하겠다.
어느 정도 이해도가 있는사람은 윗부분 핵심만 보면된다.

코드 작성 전에 import로 collections를 불러오자. 그 이유는 알고리즘/queue 부분 참고.

import collentions

han-py.tistory.com/31

Queue문제를 python으로 접근하는 세가지 방법

 

 

아래의 여러개의 코드를 비교해보자.

코드 설명은 한참 아래에 있다.

기본 코드(일반 노드가 주어진 bfs)

def bfs(v): #출발 노드
    visited = [0] * (n+1)
    que = collections.deque()
    que.append(v)
    visited[v] = 1

    while que:
        t = que.popleft()
        if # 문제조건넣기
             return #답넣기
        for w in G[t]: # 연결된 간선 탐색
            if # 제약조건 넣기
                continue
            if visited == 0: # 방문 안한거 있나 확인
                que.append(w)
                visited[v] == 1

 

visited에 거리나 가중치 추가하는 경우

def bfs(v): # 출발노드
    visited = [0] * (n+1)
    que = collections.deque()
    que.append(v)
    visited[v] = 1

    while que:
        t = que.popleft()
        if # 문제조건넣기
            return #답넣기
        for w in G[t]: # 연결된 간선 탐색
            if # 제약조건 넣기
                continue
            if visited == 0: # 방문 안한거 있나 확인
                que.append(w)
                visited[w] == visited[t] + 1 ###### 이부분 변경

 

인접행렬(i(행), j(열)로 비교하는 경우)_미로탐색

def bfs(y, x):
    visited = [[0] * (n+1) for _ in range(n+1)]
    que = collections.deque()
    que.append((y, x))  #큐에 튜플로 넣는다.
    visited[y][x] = 1
    dx = [1, -1, 0, 0]  #델타 탐색 
    dy = [0, 0, 1, -1]
    while que:
        p, q = que.popleft()
        if # 문제조건넣기
            return #답넣기
        for d in range(4): # 연결된 간선 탐색
            nx = dx[d] + q
            ny = dy[d] + p
            if # 제약조건 넣기
                continue
            if visited[ny][nx] == 0: # 방문 안한거 있나 확인
                que.append((ny, nx))
                visited[ny][nx] = visited[p][q] + 1

bfs를 공부 한 적이 있으신 분은 위의 방법으로 푸시면 됩니다.

---

 

 

그래프 탐색법

• 깊이 우선 탐색(Depth First Search, DFS)
• 너비 우선 탐색(Breadth First Search, BFS)

cf) DFS

• 탐색을 하는 과정 속에서 갈림길을 만나는 경우, 정한 규칙에 의해 한쪽으로 움직인다. ex) 갈림길 나오면 왼쪽으로만 이동.

• 재귀를 쓴다.

• 끝까지 가서 갈곳이 없으면 가장 가까운 갈림길에서 재출발한다.
  따라서 후입선출 형태의 자료구조인 stack을 활용한다.

BFS

• 인접한정점을 먼저 모두 차레로 방문 후에 방문했던 정점을 시작점으로하여 다시 인접한 정점을 차례로 방문한다.

• 선입선출 형태의 자료구조 Queue를 활용한다.

BFS의 문제종류

• 그래프가 주어지고 노드가 주어지는 경우
• 문제를 읽고 정리해 보니 그래프인 경우

BFS를 쉽게 정리

• 출발 지점으로 부터 인접정점(노드 하나 차이)을 탐색해서 queue에 넣는다.

• 출발 지점에서 2개의 노드 떨어진 지점을 탐색해서 queue에 넣는다.

• 출발 지점에서 3개의 노드 떨어진 지점을 탐색해서 queue에 넣는다.

• ......반복

• BFS는 거리 순서로 탐색을 한다.

---

 

 

BFS 코드 풀이

def bfs(v): #출발 노드
    visited = [0] * (n+1)
    que = collections.deque()
    que.append(v)
    visited[v] = 1

    while que:
        t = que.popleft()
        if # 문제조건넣기
            return #답넣기
        for w in G[t]: # 연결된 간선 탐색
            if # 제약조건 넣기
                continue
            if visited == 0: # 방문 안한거 있나 확인
                que.append(w)
                visited[v] == 1
     return 0

• visited= [0]*(n+1)
  • 노드가 1번부터 n개 까지인 경우에 사용한다.
• que = collections.deque()
  • 하나씩 넣고 빼니까 que를 사용한다. 관련 설명은 queue보고오자
• que.append(v)
  • que에 시작점 v를 넣는다. 경우에 따라 (y, x)인 튜플 형태로 들어가기도 한다.
• visited[v] = 1
  • append를 하는순간 visited에 기록한다고 외우고 풀면 편하다. 이해는 익숙해지면 자연스럽게 될꺼다.
• while que:
  • que가 비어있으면 while을 그만 반복한다. 이것도 일단 외워서 풀자
• return 0
  • while 다돌았으면 해당 되는 값이 없다는 걸 의미하므로 return값 꼭 넣어주자
  • 꼭 0이 아니여도 된다. 문제 조건에 맞게 넣어준다.

---

 

 

미로문제 풀이법

def bfs(y, x):
    visited = [[0] * (n+1) for _ in range(n)]
    que = collections.deque()
    que.append((y, x))  #큐에 튜플로 넣는다.
    visited[y][x] = 1
    dx = [1, -1, 0, 0]  #델타 탐색 
    dy = [0, 0, 1, -1]
    while que:
        p, q = que.popleft()
        if # 문제조건넣기
            return #답넣기
        for d in range(4): # 연결된 간선 탐색
            nx = dx[d] + q
            ny = dy[d] + p
            if not (0 <= nx < N and 0 <= ny < N)# 제약조건 넣기
                continue
            if visited[ny][nx] == 0: # 방문 안한거 있나 확인
                que.append((ny, nx))
                visited[ny][nx] = visited[p][q] + 1

• que 생성
• visited 생성
• que.append(y, x)는 시작점 인큐하기
• visited[y] [x] = 1 는 시작점 방문 표시
• dx, dy는 델타배열로 4방향 의 방향 표시
• p, q = que.popleft() 는 큐안에 있는 튜플 빼기

Q. 미로에서 경로의 개수와 최단거리 중 BFS에 더 적합한 문제는?

최단거리

dfs는 재귀를 이용해서 끝까지 일단가고, bfs는 출발부터 가까운 순서(level)별로 거리순으로 방문한다.

---

 

 

주어진 데이터 값 넣기(input)

지금까지는 함수 안에 bfs만 설명했다. 이제 주어지 연결 노드 넣는 법을 알아보자.

data = [[0]*(N+1) for _ in range(N+1)]

• 일단은 노드의 방향성을 넣을 이차 배열을 만들고 아래 방식으로 대입을 하자.

1. 연결노드가 모두 묶어서 주어진 경우(방향성 x)

1 2 1 3 2 4 4 2 3 5 1 2 

이런식으로 input이 주어진 경우는

Node = list(map(int, input().split())) #list로 일단 받자
for i in range(0, len(Node), 2):
    data[i][i+1] = 1
    data[i+1][i] = 1

• 이런식으로 넣어준다.

• data가 2개 넣는 이유는 방향성이 없기 때문이다.

• 만약 방향성이 있다면

  • Node = list(map(int, input().split())) #list로 일단 받자
    for i in range(0, len(Node), 2):
        data[i][i+1] = 1

    이런식으로 적어 주자.

2. 인접리스트 형태

1 2
1 3
2 4
3 5

input이 이렇게 주어지면

for _ in range(4):
    a, b = map(int, input().split())
    data[a][b] = 1
    data[b][a] = 1

이렇게 넣어주면된다

---

그래프 풀이법(3가지)_가중치 설명도 추가

1. 인접행렬(2차행렬) 인 경우

메모리가 많이 잡아먹는다....

• 이 경우는 위의 풀이라고 생각 하면된다.
• data[a][b] = 1 에서 1대신 가중치 값만 넣어주면된다.

2. 인접 리스트

static으로 정적이다.

• 원래는 linked list를 만들어야 하는데 파이썬은 그냥 하면 된다.
• 이경우는 튜플로 넣어주면된다.

# 일반 인접리스트
a = [[0], [2, 5], [3], [6, 7, 8, 9]]
####### 위의 경우는 index 값이 기준이 된거다.

• 1번 노드와 연결된 노드 - 2, 5
• 2번 노드와 연결 노드 - 3
• 이런식이다.

# 가중치 있는경우
a = [[0], [(2, 4), (5, 2)], [3, 1], ...]

3. 간선의 배열

메모리 적게 쓰지만 거의 안쓴다

그래프의 크루스칼 알고리즘 할 때만 쓰는 방법. 평소에는 안쓴다

1 2
1 3
2 4
3 4
3 5

 

 

 

추가 bfs 심화는 아래 부분이다.

han-py.tistory.com/37

[python] BFS 응용