99클럽 코테 스터디 9일차 BFS(너비 우선 탐색)

Seongbin·2024년 11월 5일

99클럽 BFS TIL 개발자취업 너비 우선 탐색 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

9/24

오늘의 학습 키워드

BFS, Breadth-First Search(깊이 우선 탐색)

이번엔 dfs 정리한 것을 바탕으로 bfs를 정리!!!

그래프 탐색이란?

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

그러면 BFS란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
- 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

너비 우선 탐색(BFS)의 특징

직관적이지 않은 면이 있다.
BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
BFS는 재귀적으로 동작하지 않는다.
이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색
일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

너비 우선 탐색(BFS)의 과정

노드(시작 노드)를 방문한다. (방문한 노드 체크)

큐에 방문된 노드를 삽입(enqueue)한다.
초기 상태의 큐에는 시작 노드만이 저장
- 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.

큐에서 꺼낸 노드를 방문한다.
큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
- 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
큐에 방문된 노드를 삽입(enqueue)한다.

큐가 소진될 때까지 계속한다.

코드로 적용해보기

1번 노드에서 시작하여 방문하고, 인접한 모든 노드를 큐에 넣습니다.
큐 상태: [2, 3]
큐에서 2번 노드를 꺼내 방문하고, 인접한 모든 노드를 큐에 넣습니다.
큐 상태: [3, 6, 4]
큐에서 3번 노드를 꺼내 방문하고, 인접한 모든 노드를 큐에 넣습니다.
큐 상태: [6, 4, 7, 5]
큐에서 6번 노드를 꺼내 방문합니다. 6번은 더 이상 방문할 인접 노드가 없습니다.
큐 상태: [4, 7, 5]
큐에서 4번 노드를 꺼내 방문합니다. 4번도 더 이상 방문할 인접 노드가 없습니다.
큐 상태: [7, 5]
큐에서 7번 노드를 꺼내 방문합니다. 7번도 더 이상 방문할 인접 노드가 없습니다.
큐 상태: [5]
마지막으로 5번 노드를 큐에서 꺼내 방문합니다. 5번도 더 이상 방문할 인접 노드가 없습니다.
큐 상태: []
큐가 비었으므로 BFS 탐색이 끝났습니다.

BFS 탐색 순서는 다음과 같습니다: 1 -> 2 -> 3 -> 6 -> 4 -> 7 -> 5

from collections import deque

def bfs(graph, start):
    # 방문한 노드를 기록하기 위한 리스트
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()  # 큐에서 첫 번째 노드를 꺼냄
        print(v, end=' ')

        # 현재 노드와 연결된 노드를 모두 확인 (번호가 낮은 순서부터 처리)
        for i in sorted(graph[v]):
            if not visited[i]:
                queue.append(i)  # 방문하지 않은 노드는 큐에 추가
                visited[i] = True

# 그래프 정보 (DFS 코드와 동일)
graph = [
    [],         # 0번 노드는 사용하지 않음
    [2, 3, 7],  # 1번 노드는 2, 3, 7번 노드와 연결
    [1, 4, 6],  # 2번 노드는 1, 4, 6번 노드와 연결
    [1, 5, 7],  # 3번 노드는 1, 5, 7번 노드와 연결
    [2, 6],     # 4번 노드는 2, 6번 노드와 연결
    [3, 7],     # 5번 노드는 3, 7번 노드와 연결
    [2, 4],     # 6번 노드는 2, 4번 노드와 연결
    [1, 3]      # 7번 노드는 1, 3번 노드와 연결
]

print("방문 순서:")
bfs(graph, 1)

출력 :
방문순서
1 2 3 6 4 7 5

graph 변수는 그래프를 인접 리스트(adjacency list) 방식으로 표현
인접 리스트는 그래프를 저장하는 방법 중 하나로, 각 노드에 연결된 다른 노드들을 리스트 형태로 저장
이 방식은 메모리 효율성이 좋아서, 그래프의 간선 수가 많지 않을 때 특히 유용합니다. 즉, 그래프가 희소할 때 (즉, 간선의 수가 적을 때) 메모리 사용량이 효율적이며, 간선의 수가 많을 때는 인접 행렬 방식보다 비효율적일 수 있습니다.

BFS 함수

graph와 start를 인자로 받아 시작 노드에서부터 너비 우선 탐색을 진행
visited 리스트는 각 노드가 방문되었는지를 기록하기 위한 것으로, 노드의 수만큼 False로 초기화합니다.
deque를 이용해 큐를 구현하였고, 시작 노드를 큐에 추가하고 visited 리스트에 방문 표시를 합니다.

탐색 과정

while queue: 반복문은 큐가 빌 때까지 실행됩니다.
v = queue.popleft()는 큐에서 첫 번째 노드를 꺼내어 현재 방문 중인 노드를 기록합니다.
for i in sorted(graph[v]):는 현재 노드 v와 연결된 모든 노드를 번호가 낮은 순서대로 확인하는 루프입니다.
방문하지 않은 노드를 큐에 추가하고 방문 표시를 합니다.

오늘의 문제

백준 7562번

https://www.acmicpc.net/problem/7562

문제 설명

입출력 예

BFS 탐색 순서

오름차순 방문: BFS 탐색 시 인접 정점들을 오름차순으로 방문.

나이트의 시작 위치에서 BFS 탐색을 시작한다. 시작 위치는 (now_x, now_y)로, 이 위치를 큐에 넣고 방문 처리를 한다.
큐에서 (x, y, cnt)를 꺼내 현재 위치에서 이동하려는 목표 위치 (move_x, move_y)와 일치하는지 확인한다.

만약 일치하면, 해당 지점까지의 이동 횟수 cnt를 출력하고 탐색을 종료한다.

나이트가 이동할 수 있는 8개의 방향을 모두 확인한다.

각 방향으로 이동 가능한 경우 (0 <= nx < i와 0 <= ny < i 조건을 만족하고 아직 방문하지 않은 경우), 해당 위치를 큐에 추가하고 방문 처리를 한다.

큐가 빌 때까지 위 과정을 반복하며 목표 위치에 도달하는 최소 횟수를 찾는다.
모든 경우를 탐색한 후 목표 위치에 도달하지 못하면 탐색을 종료한다.

BFS 탐색 순서 예시

탐색 과정 예시 (입력: (0, 0)에서 (7, 0)까지 이동)
탐색 과정 (5번의 이동)

첫 번째 이동:
시작 위치 (0, 0)에서 이동 가능한 8개의 방향 중 (2, 1)과 (1, 2)로 이동할 수 있다.
이 경우, (2, 1)으로 이동한다고 가정한다. 현재 이동 횟수는 1.
두 번째 이동:
위치 (2, 1)에서 이동 가능한 8개의 방향 중 (4, 2)로 이동한다.
이동 횟수는 2.
세 번째 이동:
위치 (4, 2)에서 이동 가능한 8개의 방향 중 (6, 3)으로 이동한다.
이동 횟수는 3.
네 번째 이동:
위치 (6, 3)에서 이동 가능한 방향 중 (7, 5)로 이동한다.
이동 횟수는 4.
다섯 번째 이동:
위치 (7, 5)에서 최종 목표인 (7, 0)으로 이동한다.
이동 횟수는 5.
따라서 최소 이동 횟수는 5번입니다.

1. 기본 설정 및 입력 처리

from collections import deque

dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

n = int(input())
for _ in range(n):
    i = int(input())
    now_x, now_y = map(int, input().split())
    move_x, move_y = map(int, input().split())

from collections import deque : BFS 탐색을 위해 큐를 사용해야 하므로 deque를 임포트한다.
dx와 dy 리스트는 나이트가 이동할 수 있는 8개의 방향을 정의한다.
n = int(input()): 테스트 케이스의 개수를 입력받는다.
각 테스트 케이스마다 체스판의 크기 i와 나이트의 현재 위치 (now_x, now_y) 및 목표 위치 (move_x, move_y)를 입력받는다.

2. BFS 탐색 정의 및 초기화

	q = deque([(now_x, now_y, 0)])
    visit = [[False] * i for _ in range(i)]
    visit[now_x][now_y] = True

q = deque([(now_x, now_y, 0)]): 큐를 생성하고 나이트의 현재 위치와 이동 횟수 0을 초기값으로 넣는다.
visit = [[False] * i for _ in range(i)]: 체스판의 각 위치에 대해 방문 여부를 기록하는 2차원 리스트를 생성한다. 초기값은 모두 False로 설정한다.
visit[now_x][now_y] = True : 나이트의 현재 위치를 방문 처리한다.

3. BFS 탐색 과정 및 출력

	    while q:
          x, y, cnt = q.popleft()
          if x == move_x and y == move_y:
              print(cnt)
              break
          for j in range(8):
              nx, ny = x + dx[j], y + dy[j]
              if 0 <= nx < i and 0 <= ny < i and not visit[nx][ny]:
                  visit[nx][ny] = True
                  q.append((nx, ny, cnt + 1))

while q: 큐가 빌 때까지 반복하여 BFS 탐색을 진행한다.
x, y, cnt = q.popleft() : 큐에서 현재 위치와 이동 횟수를 꺼낸다.
if x == move_x and y == move_y : 현재 위치가 목표 위치와 일치하면 이동 횟수 cnt를 출력하고 탐색을 종료한다.
for j in range(8) :나이트가 이동할 수 있는 8개의 방향을 모두 확인한다.
nx, ny = x + dx[j], y + dy[j] : 각 방향으로의 새로운 위치를 계산한다.
if 0 <= nx < i and 0 <= ny < i and not visit[nx][ny] : 새로운 위치가 체스판 안에 있고 아직 방문하지 않은 경우에만 이동한다.
visit[nx][ny] = True : 새로운 위치를 방문 처리한다.
q.append((nx, ny, cnt + 1)) : 새로운 위치와 이동 횟수를 큐에 추가한다.

전체 풀이

from collections import deque

dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

n = int(input())
for _ in range(n):
    i = int(input())
    now_x, now_y = map(int, input().split())
    move_x, move_y = map(int, input().split())

    q = deque([(now_x, now_y, 0)])
    visit = [[False] * i for _ in range(i)]
    visit[now_x][now_y] = True

    while q:
        x, y, cnt = q.popleft()
        if x == move_x and y == move_y:
            print(cnt)
            break
        for j in range(8):
            nx, ny = x + dx[j], y + dy[j]
            if 0 <= nx < i and 0 <= ny < i and not visit[nx][ny]:
                visit[nx][ny] = True
                q.append((nx, ny, cnt + 1))