[Coding Test]BFS

용어

- 용어 정의

BFS(너비 우선 탐색, Breadth-First Search)

그래프 탐색 알고리즘 중 하나로, 그래프의 각 노드를 “넓게” 탐색해 나가는 방식입니다. BFS는 최단 경로를 찾는 데 유용하고, 큐(Queue)를 이용하여 구현합니다.

- BFS의 특징

• 큐(Queue)를 사용하여 구현합니다.
• 같은 깊이에 있는 노드를 먼저 방문한 뒤, 점차 깊이를 늘려가며 탐색합니다.
• BFS는 최단 경로를 보장합니다(단, 그래프가 unweighted일 경우).
• 각 노드를 한 번씩만 방문합니다.
• BFS 알고리즘 동작 과정:
• 시작 노드를 큐에 넣고 방문 표시를 합니다.
• 큐에서 노드를 꺼내서 해당 노드와 연결된 노드를 큐에 넣습니다.
• 큐가 빌 때까지 이 과정을 반복합니다.

예제 1

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 기록할 집합
    queue = deque([start])  # 큐에 시작 노드 넣기
    visited.add(start)  # 시작 노드를 방문했다고 표시

    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        print(node, end=" ")  # 방문한 노드 출력

        # 현재 노드와 연결된 모든 노드를 큐에 추가
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 그래프 예제 (인접 리스트 형식)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2],
    6: [3]
}

# BFS 실행
bfs(graph, 1)

1 2 3 4 5 6 

- 한줄씩

start = 1

visited = set()  # 방문한 노드를 기록할 집합
visited

set()

queue = deque([start])  # 큐에 시작 노드 넣기
queue

deque([1])

visited.add(start)  # 시작 노드를 방문했다고 표시
visited

{1}

while queue:

node = queue.popleft()  # 큐에서 노드를 꺼냄
node

1

print(node, end=" ")  # 방문한 노드 출력

1 

# 현재 노드와 연결된 모든 노드를 큐에 추가
for neighbor in graph[node]:

neighbor = graph[node]
neighbor

[2, 3]

if 2 not in visited:
    visited.add(2)
    queue.append(2)
visited,queue

({1, 2}, deque([2]))

if 3 not in visited:
    visited.add(3)
    queue.append(3)
visited,queue

({1, 2, 3}, deque([2, 3]))

예제 2

- 최단 경로 찾기 (BFS 응용)

BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용합니다. 예를 들어, 출발점에서 목표 지점까지의 최단 거리를 계산하는 문제에서 BFS를 사용할 수 있습니다.

from collections import deque

def bfs_shortest_path(graph, start, target):
    visited = set()  # 방문한 노드를 기록할 집합
    queue = deque([(start, [start])])  # 큐에 시작 노드와 경로를 튜플로 넣음

    while queue:
        node, path = queue.popleft()

        if node == target:  # 목표 노드를 찾으면 경로를 반환
            return path

        visited.add(node)

        # 현재 노드와 연결된 모든 노드를 큐에 추가
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))

    return None  # 목표 노드가 없으면 None을 반환

# 그래프 예제 (인접 리스트 형식)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 최단 경로 찾기
shortest_path = bfs_shortest_path(graph, 'A', 'F')
print("최단 경로:", shortest_path)

최단 경로: ['A', 'C', 'F']

- 한줄씩

start, target = 'A', 'F'

visited = set()  # 방문한 노드를 기록할 집합
visited

set()

queue = deque([(start, [start])])  # 큐에 시작 노드와 경로를 튜플로 넣음
queue

deque([('A', ['A'])])

queue 가 True 일때까지 진행

while queue:

node, path = queue.popleft()
node, path 

('A', ['A'])

# if node == target:  # 목표 노드를 찾으면 경로를 반환
#return path

visited.add(node)
visited

{'A'}

graph[node]

['B', 'C']

if 'B' not in visited:
    queue.append(('B', 'A' + 'B'))
queue

deque([('B', 'AB')])

if 'C' not in visited:
    queue.append(('C', 'A' + 'C'))
queue

deque([('B', 'AB'), ('C', 'AC')])

from collections import deque

def bfs_shortest_path(graph, start, target):
    visited = set()  # 방문한 노드를 기록할 집합
    queue = deque([(start, [start])])  # 큐에 시작 노드와 경로를 튜플로 넣음

    while queue:
        print(queue)
        node, path = queue.popleft()

        if node == target:  # 목표 노드를 찾으면 경로를 반환
            return path
        print(visited)
        visited.add(node)

        # 현재 노드와 연결된 모든 노드를 큐에 추가
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))
            print(f'for 문 neighbor{neighbor}')
            print(f'for 문 queue{queue}')

    return None  # 목표 노드가 없으면 None을 반환

# 그래프 예제 (인접 리스트 형식)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 최단 경로 찾기
shortest_path = bfs_shortest_path(graph, 'A', 'F')
print("최단 경로:", shortest_path)

deque([('A', ['A'])])
set()
for 문 neighborB
for 문 queuedeque([('B', ['A', 'B'])])
for 문 neighborC
for 문 queuedeque([('B', ['A', 'B']), ('C', ['A', 'C'])])
deque([('B', ['A', 'B']), ('C', ['A', 'C'])])
{'A'}
for 문 neighborA
for 문 queuedeque([('C', ['A', 'C'])])
for 문 neighborD
for 문 queuedeque([('C', ['A', 'C']), ('D', ['A', 'B', 'D'])])
for 문 neighborE
for 문 queuedeque([('C', ['A', 'C']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])])
deque([('C', ['A', 'C']), ('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])])
{'A', 'B'}
for 문 neighborA
for 문 queuedeque([('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E'])])
for 문 neighborF
for 문 queuedeque([('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('F', ['A', 'C', 'F'])])
deque([('D', ['A', 'B', 'D']), ('E', ['A', 'B', 'E']), ('F', ['A', 'C', 'F'])])
{'A', 'B', 'C'}
for 문 neighborB
for 문 queuedeque([('E', ['A', 'B', 'E']), ('F', ['A', 'C', 'F'])])
deque([('E', ['A', 'B', 'E']), ('F', ['A', 'C', 'F'])])
{'D', 'A', 'B', 'C'}
for 문 neighborB
for 문 queuedeque([('F', ['A', 'C', 'F'])])
for 문 neighborF
for 문 queuedeque([('F', ['A', 'C', 'F']), ('F', ['A', 'B', 'E', 'F'])])
deque([('F', ['A', 'C', 'F']), ('F', ['A', 'B', 'E', 'F'])])
최단 경로: ['A', 'C', 'F']

예제 3

def bfs_maze(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 동, 남, 서, 북
    queue = deque([(start, 0)])  # (위치, 거리)
    visited = set()
    
    visited.add(start)
    
    while queue:
        (x, y), distance = queue.popleft()
        
        if (x, y) == goal:
            return distance
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append(((nx, ny), distance + 1))
                visited.add((nx, ny))
    
    return -1  # 목표에 도달할 수 없는 경우

maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
goal = (4, 4)

print("최단 거리:", bfs_maze(maze, start, goal))

최단 거리: 8

- 한 줄씩

rows, cols = len(maze), len(maze[0])
rows, cols

(5, 5)

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 동, 남, 서, 북
directions

[(0, 1), (1, 0), (0, -1), (-1, 0)]

queue = deque([(start, 0)])  # (위치, 거리)
queue

deque([((0, 0), 0)])

visited = set()
visited

set()

visited.add(start)
visited

{(0, 0)}

while queue:

(x, y), distance = queue.popleft()
(x, y), distance

((0, 0), 0)

if (x, y) == goal:
    # return distance
    print(True)

for dx, dy in directions:
    print(dx, dy)
    nx, ny = x + dx, y + dy

0 1
1 0
0 -1
-1 0

if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and (nx, ny) not in visited:
    queue.append(((nx, ny), distance + 1))
    visited.add((nx, ny))

queue,visited

(deque([]), {(0, 0)})

- print 해보기

def bfs_maze(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 동, 남, 서, 북
    queue = deque([(start, 0)])  # (위치, 거리)
    visited = set()
    
    visited.add(start)
    print(f'처음 방문 {visited}')
    while queue:
        (x, y), distance = queue.popleft()
        
        if (x, y) == goal:
            return distance
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append(((nx, ny), distance + 1))
                visited.add((nx, ny))
                print(nx,ny)
    
    return -1  # 목표에 도달할 수 없는 경우

maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
goal = (4, 4)

bfs_maze(maze, start, goal)

처음 방문 {(0, 0)}
1 0
2 0
2 1
3 0
2 2
4 0
1 2
4 1
0 2
4 2
0 3
4 3
0 4
4 4
1 4

8

예제 4

섬의 개수 구하기

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def bfs(x, y):
        queue = deque([(x, y)])
        visited[x][y] = True

        while queue:
            cx, cy = queue.popleft()
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1 and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True

    island_count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
                island_count += 1

    return island_count

grid = [
    [1, 1, 0, 0, 0],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 0, 0]
]

print("섬의 개수:", count_islands(grid))

섬의 개수: 3

- 한 줄씩

rows, cols = len(grid), len(grid[0])
rows, cols

(4, 5)

visited = [[False] * cols for _ in range(rows)]
visited

[[False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False]]

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
directions

[(0, 1), (1, 0), (0, -1), (-1, 0)]

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    
    cx, cy = queue.popleft()
    
    for dx, dy in directions:
        nx, ny = cx + dx, cy + dy
        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1 and not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

while queue:

island_count = 0

for i in range(rows):
    for j in range(cols):

i=0
j=0

if grid[i][j] == 1 and not visited[i][j]:
    bfs(i, j)
    island_count += 1
island_count

1

- 결과 하나씩

def count_islands(grid):
    # rows, cols: 격자의 행과 열의 개수를 저장합니다.
    rows, cols = len(grid), len(grid[0])
    # visited 리스트: 각 위치의 방문 여부를 기록합니다.
    visited = [[False] * cols for _ in range(rows)]
    # directions 리스트: 현재 위치에서 상하좌우 탐색을 위한 방향 정보를 나타냅니다.
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # (0, 1): 오른쪽
    # (1, 0): 아래쪽
    # (0, -1): 왼쪽
    # (-1, 0): 위쪽

    # bfs(x, y) 함수: 특정 육지에서 시작하여 연결된 모든 육지를 탐색하고 방문합니다.
    def bfs(x, y):
        # 큐(queue)에 시작 좌표 (x, y)를 추가합니다.
        queue = deque([(x, y)])
        visited[x][y] = True

        # 큐가 빌 때까지 연결된 모든 육지를 탐색하며 방문 여부를 기록합니다.
        while queue:
            # (0,0)에서 첫 번째 1을 발견하고 BFS 탐색을 시작합니다.
            # 이 위치와 연결된 (0,1) 및 (1,0) 위치도 큐에 추가되고 방문됩니다.
            # (1,3)에서 두 번째 1을 발견하면 BFS 탐색을 통해 (1,4)와 (2,3)을 방문합니다.
            # 큐가 빌 때까지 상하좌우 연결된 육지를 탐색하며 방문합니다.
            # 방문한 위치는 다시 탐색하지 않도록 visited에 표시합니다.
            cx, cy = queue.popleft()
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1 and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True

    island_count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1 and not visited[i][j]:
                bfs(i, j) # 연결된 육지 탐색
                print(f'육지를 탐색한 좌표 {i,j}')
                island_count += 1 # 새로운 섬 발견 시 개수 증가
                
    # 격자의 모든 위치를 순회하며 아직 방문하지 않은 육지를 발견할 때마다 BFS 탐색을 수행합니다.
    # BFS 탐색이 끝난 후 island_count를 증가시켜 섬 개수를 기록합니다.

    return island_count

• 1은 육지를 나타내며, 상하좌우로 연결된 1은 하나의 섬입니다.
• 이 예제에서는 총 3개의 섬이 있습니다:
• 첫 번째 섬: (0,0), (0,1), (1,0)
• 두 번째 섬: (1,3), (1,4), (2,3)
• 세 번째 섬: (3,1), (3,2)

grid = [
    [1, 1, 0, 0, 0],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 0, 0]
]

print("섬의 개수:", count_islands(grid))

육지를 탐색한 좌표 (0, 0)
육지를 탐색한 좌표 (1, 3)
육지를 탐색한 좌표 (3, 1)
섬의 개수: 3

• BFS를 선택한 이유
• BFS는 가까운 노드부터 탐색하므로 섬의 각 부분을 효율적으로 탐색할 수 있습니다.
• 모든 연결된 육지를 한 번에 탐색하며 이미 방문한 위치를 다시 탐색하지 않기 때문에 탐색 중복을 방지합니다.

예제 5

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque

def level_order_traversal(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

# 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print("레벨별 탐색 결과:", level_order_traversal(root))

레벨별 탐색 결과: [[1], [2, 3], [4, 5, 6]]

- 한 줄씩

트리를 만드는 과정

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

if not root:
    return []

result = []
result

[]

queue = deque([root])
queue

deque([<__main__.TreeNode at 0x7f9463197040>])

while queue:
    level = []
    for _ in range(len(queue)):
        node = queue.popleft()
        level.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    result.append(level)
result

[[1], [2, 3], [4, 5, 6]]

- 설명

• 아래 이진구조

   1
  / \

  2 3 /  
  4 5 6

# TreeNode 클래스는 각 노드를 나타냅니다.
class TreeNode:
    # 각 노드는 값을 저장하는 val, 왼쪽 자식을 가리키는 left, 오른쪽 자식을 가리키는 right 속성을 가집니다.
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 탐색을 위해 큐(queue)를 사용합니다. 큐는 deque를 통해 효율적으로 구현됩니다.
# 트리가 비어 있는 경우 빈 리스트를 반환합니다.
from collections import deque

def level_order_traversal(root):
    if not root:
        return []

    # result: 각 레벨의 탐색 결과를 저장합니다.
    result = []
    # queue: 현재 탐색할 노드들을 저장합니다. 처음에는 루트 노드 root만 포함합니다.
    queue = deque([root])

    # 큐 순회: 큐에 있는 노드를 하나씩 꺼내 현재 레벨의 노드 값(node.val)을 level 리스트에 추가합니다.
    while queue:
        # 각 레벨에 대해 현재 큐의 길이만큼 반복하여 해당 레벨의 모든 노드를 탐색합니다.
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            
            # 현재 노드가 왼쪽 또는 오른쪽 자식을 가지면 그 자식을 큐에 추가합니다.
            if node.left:
                queue.append(node.left)
            # 이렇게 하면 다음 레벨의 노드들이 큐에 저장됩니다.
            if node.right:
                queue.append(node.right)
        result.append(level)
        print(f'레벨 {result}')

    return result

# 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print("레벨별 탐색 결과:", level_order_traversal(root))

레벨 [[1]]
레벨 [[1], [2, 3]]
레벨 [[1], [2, 3], [4, 5, 6]]
레벨별 탐색 결과: [[1], [2, 3], [4, 5, 6]]

• 큐 상태 변화:

• Level 1: [1] => 큐에 [2, 3] 추가

• Level 2: [2, 3] => 큐에 [4, 5, 6] 추가

• Level 3: [4, 5, 6] => 큐 비어있음 (탐색 종료)

• BFS 선택 이유

• BFS는 레벨 순서 탐색에 적합합니다.

• 각 레벨을 탐색하면서 자연스럽게 층별 탐색 결과를 얻을 수 있습니다.