본문 바로가기

Algorithm 💡/BFS42

[백준 2468번] 안전 영역 from collections import deque # 2차원 배열의 행과 열 개수 n = int(input()) # 지역 높이 정보(2차원 배열) area = [] visited = [[False]*n for _ in range(n)] count_list = [] solution = 0 for _ in range(n): area.append(list(map(int,input().split()))) max_value = max(map(max,area)) def bfs(x,y,value): if visited[x][y] or (area[x][y]-value) = 0 and temp_x = 0 and temp_y < n: if (area[temp_x][temp_y] - valu.. 2023. 2. 15.
[백준 2644번] 촌 수 계산 from collections import deque # 전체 사람 수(n) n = int(input()) # 촌수를 계산해야 하는 두 사람 target_a, target_b = map(int,input().split()) # 부모 자식들 간의 관계의 개수 m = int(input()) # 전체 사람의 부자 관계를 나타내는 2차원 리스트 graph = [[] for _ in range(n+1)] # 확인 여부 확인용 리스트 visited = [False] * (n+1) # 친척 관계를 저장하는 리스트 relation = [0]*(n+1) relation[target_a] = 0 for _ in range(m): x, y = map(int,input().split()) graph[x].append(y) g.. 2023. 2. 15.
[백준 10026번] 적록색약 from collections import deque n = int(input()) # 영역(2차원 리스트) area = [] # 적록색약이 아닌 사람의 구역의 수 count_a = 0 # 적록색약인 사람의 구역의 수 count_b = 0 for _ in range(n): area.append(list(input())) # 적록색약 X 방문 여부 2차원 리스트 visited_a = [[False]*n for _ in range(n)] # 적록색약 O 방문 여부 2차원 리스트 visited_b = [[False]*n for _ in range(n)] # 적록색약 X BFS함수 def bfs_a(x,y): if visited_a[x][y]: return False visited_a[x][y] = True q.. 2023. 2. 14.
[백준 7576번] 토마토 from collections import deque # 가로(m), 세로(n) m, n = map(int,input().split()) # 토마토가 담긴 상자(2차원 리스트) area = [] # 토마토가 존재하는 위치를 담는 리스트 exist_list = [] # 토마도가 모두 익는 최소 일수(정답) result = 0 # BFS 함수 def bfs(list): global result queue = deque(list) # 익을 수 있는 토마토가 다 익었을 때, 마지막 구역에 저장된 값 depth = 0 while queue: v = queue.popleft() nx = [-1,1,0,0] ny = [0,0,-1,1] for i in range(4): temp_x = v[0] + nx[i] temp.. 2023. 2. 14.
[백준 2178번] 미로 탐색 from collections import deque n,m = map(int,input().split()) # n x m 크기의 미로 maze = [] # 방문 여부 확인용 2차원 배열 visited = [[False]*m for _ in range(n)] # 미로 입력받고 저장 for _ in range(n): maze.append(list(map(int,input()))) # bfs 함수 def bfs(x,y): # 방문 처리 visited[x][y] = True # queue 자료구조 선언 queue = deque([(x,y)]) while queue: v = queue.popleft() vx = v[0] vy = v[1] nx = [-1,1,0,0] ny = [0,0,-1,1] # 상-하-좌-우.. 2023. 2. 12.
[BFS] BFS 알고리즘의 개념 및 동작과정 / DFS와 BFS 선정 기준 BFS는 Breadth-First Search, 너비 우선 탐색이라고 부르며 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 Queue 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. BFS 알고리즘의 동작 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 너비 우선 탐색 알고리즘인 BFS는 Queue 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현 함에 .. 2023. 2. 11.

티스토리툴바