[[Algorithm] ] BFS 알고리즘 기본 함수 작성 방법 (파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다.

 

오늘 작성할 내용은 굉장히 간단한 문제지만, 제가 간과하고 있던 부분이라 따로 작성하게 됐습니다.

BFS알고리즘을 함수로 만들때, 탐색조건을 작성하는 순서가 매우 중요하다는 것입니다.

 

결론부터 말씀드리면, BFS알고리즘 함수 정의 시,

1. def bfs(x,y):

2. q = deque() 선언

3.q에 x,y 담기(append)

4. while q

5. x,y = q.popleft()

6. for i in range(4) (동서남북 방향 탐색) 

-------여기 까진 알던 내용 -------

7. if 범위 이탈, continue

8. if 갈 수 없는 영역, continue

9. if 갈 수 있는 영역, 방문처리 & q.append((방문 인덱스))

 

간단하게 작성했지만, 7,8,9의 순서를 지키는 것이 중요합니다. 8,9번은 그렇다고 치고, 7번은 무조건 앞에 나와야합니다.

그렇지 않을 시 아래와 같은 에러코드가 등장함을 알 수 있습니다.

BFS 알고리즘 예제

NxM 그래프에서 (1,1)(왼쪽 위) -> (N,M) (오른쪽 아래)로 가는 최단거리를 구하시오. (단, 못가는 경우는 없음)

#정상 작동하는 코드#
from collections import deque

n,m = map(int, input().split())
graph = [ list(map(int,input())) for i 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 or 0 > ny or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                q.append((nx,ny))
    return graph

print(bfs(0,0))

 

위와 같이 코드를 작성하면 정상동작하는 것을 알 수 있지만,, 만약 아래와 같이 코드를 작성한 경우..

범위에서 벗어난 값을 먼저 걸러주지 않을 경우, 이런 에러를 확인할 수 있습니다.

#잘못된 코드!!!#
from collections import deque

n,m = map(int, input().split())
graph = [ list(map(int,input())) for i 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]
# graph[nx][ny]는 값을 알 수 없으므로 true/false를 판단할 수 없다.
            if graph[nx][ny] == 0:
                continue
            if 0 > nx or 0 > ny or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                q.append((nx,ny))
    return graph

print(bfs(0,0))

---

추가적으로, BFS 알고리즘의 경우 최단 경로의 거리를 구하는 문제가 많이 출제되는데요.

보통은 위와 같은 알고리즘으로 기존의 값에 +1을 더하여 거리를 계산하지만, 이런 경우 시작점의 값이 본래값이 아닌 다른 값이 나오는 걸 확인할 수 있습니다.

 

5x6인 graph 리스트를 아래와 같이 input 한 후 위와 동일한 bfs 알고리즘((1,1) -> (n,m)까지 거리 구하기) 을 적용했다고

가정하겠습니다.

위처럼 graph[0][0] = 본래 1이므로, 1을 유지해야하지만, 코드 상 (0,0)에서 상하좌우가 더해진 값부터 bfs함수가 실질적으로 적용되므로, 1이 아닌 3으로 나타나게 됩니다.

 

해결책은,,좀 더 공부해봐야할 듯 합니다..

 

감사합니다.