BFS

bfs는 넓이 우선 탐색이다. dfs는 찾을 수 있는 가장 깊은 단계까지 갔다가 다시 돌아온 뒤 그 과정을 반복하는 과정인 반면, bfs는 찾을 수 있는 가장 넓은 단계까지 갔다가 돌아온 뒤 그 과정을 반복하는 알고리즘이다.

dfs는 첫번째 방문한 노드에 이어져 있는 노드를 모두 방문한 뒤 다시 이어져 있던 노드의 첫 번째 노드부터 방문하기 때문에 큐 자료구조를 활용해서 구현할 수 있다.

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited


assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]

bfs로 구현한 섬의 개수
원리는 dfs와 같다

def island_bfs(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
        # 섬이 존재하지 않는다면 루프문 통과
            if grid[row][col] != '1':
                continue
		# 섬이 존재한다면 cnt를 1 증가시켜준 뒤
            cnt += 1
            # 큐에 방문한 지점을 집어넣고
            q = deque([(row, col)])
		
        	# 큐에 지점이 존재하는 동안 그 큐 근처의 지점을 순서대로 방문
            while q:
                x, y = q.popleft()
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # 방문할 가치가 없을 시 continue
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    # 방문 표시
                    grid[nx][ny] = '0'
                    # 인접 지점 큐에 넣기
                    q.append((nx, ny))
    return cnt


assert island_bfs(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_bfs(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

숙제

• 1) 상위 K 빈도 요소
  • Q. 문제 설명 ❓ 상위 k번 이상 등장하는 요소를 추출해보세요.
• 입력

nums = [1, 1, 1, 2, 2, 3], k=2

• 출력

[1,2]

답

import heapq

def k_ele(arr, k):
  li = []
  for i in range(len(arr)):
    li.append(0)
  
  for i in arr:
    li[i] += 1
  heapq.heapify(li)
  li.reverse()
  for i in range(k):
    print(i + 1)

• 2) 부분 집합
  • Q. 문제 설명 ❓ 모든 부분 집합을 리턴하라.
• 입력
  

nums = [1, 2, 3]

• 출력

[
	[3],
	[1],
	[2],
	[1,2,3],
	[1,3],
	[2,3],
	[1,2],
	[]
]

답

import itertools as it

nums = [1, 2, 3]

for i in range(len(nums) + 1):
  li = list(it.combinations(nums,i))
  for j in li:
    print(list(j))

• itertools 사용 x

nums = [1,2,3]
li = []

for i in range(len(nums) + 1):
  for j in range(len(nums) + 1):
    if j > i:
      li.append(nums[i:j])
li.append([])

print(li)