BFS 너비 우선 탐색 - 코드 템플릿

BFS 코드

def bfs(S, E):
    queue = [S]
    visited = [0] * (V + 1)
    visited[S] = 1  # 방문 표시: 거리

    while queue:
        c = queue.pop(0)

        # 이 부분에서 정답 처리!
        if (정답 조건):
            return answer
            # 거리: visited[c] - 1 (시작 노드 제외)
            # 가능 여부: 1

        for n in (탐색할 영역):  # 연결된 노드, 4방향, 8방향, 조건 등
            if visited[n] == 0:  # 미방문
                queue.append(n)
                visited[n] = 방문 표시
                # 거리: visited[c] + 1
                # 방문: 1

    return 0  # 불가능

 

 

정답 조건

아래는 "(정답 조건)" 부분에 대한 코드를 구현한 것이다.

# 도착 지점에 도달한 경우
if c == E:

 

 

탐색할 영역

아래는 "(탐색할 영역)" 부분에 대한 코드를 구현한 것이다.

# 연결된 노드
# lst: 그래프
for n in lst[c]:
	

# 4방향 탐색
for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
	ni, nj = ci + di, cj + dj