본문 바로가기

BFS3

프로그래머스 | Python | 완전탐색 | 전력망을 둘로 나누기 (Lv.2) https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 해결: 트리 분할 후 완전 탐색정답 코드(BFS)from collections import dequedef bfs(node, graph, visited): count = 0 queue = deque([node]) visited[node] = True while queue: current = queue.popleft() count += 1 for neighbor in graph[c.. 2025. 2. 12.
BFS와 DFS: 언제 하나만 사용할 수 있을까? BFS와 DFS: 언제 하나만 사용할 수 있을까?알고리즘을 공부하다 보면 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)가 모두 가능한 문제를 자주 접하게 됩니다. 하지만 일부 문제들은 BFS로만 풀어야 하거나, DFS로만 풀어야 하는 경우도 존재합니다.이번 글에서는 "오직 BFS 또는 DFS로만 풀 수 있는 문제"를 정리해 보겠습니다.1️⃣ BFS로만 풀 수 있는 문제 유형BFS(너비 우선 탐색)는 최단 거리, 최단 횟수를 찾는 문제에서 반드시 사용됩니다.이유는 BFS는 탐색을 진행할 때, 가까운 노드부터 차례대로 탐색하기 때문입니다.✅ BFS로만 풀 수 있는 문제 유형 유형  설명 최단 거리 탐색그래프에서 한 지점에서 다른 지점까지의 최소 이동 횟수를 구하는 문제가중치가 없는 그래프에서 최단 경로.. 2025. 2. 12.
프로그래머스 | Python | BFS | 게임 맵 최단거리 (Lv.2) https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr정답코드from collections import dequedef solution(maps): # 맵 크기: n은 행(row)의 개수, m은 열(column)의 개수 n, m = len(maps), len(maps[0]) # 이동 방향 (상, 하, 좌, 우) # dx: 행 방향, dy: 열 방향 dx = [-1, 1, 0, 0] # 위로(-1), 아래로(+1), 그대로(0), 그대로(0) dy = [0, 0.. 2025. 2. 9.

티스토리툴바