민혁이의 IT스토리

https://www.acmicpc.net/problem/2178 문제 풀이 전략 BFS(Breadth-First Search) 활용: 최단 경로 문제에서는 현재 위치에서 가까운 곳부터 탐색하는 BFS가 적합합니다. DFS는 경로가 존재함을 확인하기엔 좋으나, 최단 거리를 보장하기 위해 별도의 처리가 필요하기 때문입니다.방문 처리와 거리 계산의 통합: 별도의 방문 리스트(visited)를 만들 수도 있지만, 입력받은 미로 리스트 자체에 지금까지 이동한 거리(Step)를 직접 갱신하면 메모리를 아끼고 방문 여부도 동시에 체크할 수 있습니다. 해결 과정데이터 입력: 미로를 2차원 리스트로 입력받습니다. (이때 숫자가 붙어서 들어오므로 list(input())을 활용해 하나씩 쪼개줍니다.)Queue 초기화:..

BFS란?그래프 탐색 알고리즘 중 하나로, 시작 정점에서 가까운 노드부터 차례대로 탐색해 나가는 방식입니다.즉, "넓게 퍼져나가듯" 탐색한다고 해서 너비 우선 탐색이라고 부릅니다. 동작 원리시작 노드를 큐(Queue)에 넣는다.큐에서 노드를 꺼내서 방문한다.방문한 노드의 인접한 노드들을 모두 큐에 넣는다.큐가 빌 때까지 2~3 과정을 반복한다. BFS의 특징 큐(Queue) 사용: FIFO 구조로 탐색 순서를 보장가까운 노드부터 탐색: 레벨별 탐색이 가능최단 경로 탐색에 유리: 가중치가 없는 그래프에서 최단 거리를 찾을 때 많이 사용 마무리BFS는 그래프나 트리에서 가장 기본적인 탐색 알고리즘으로,큐를 활용해 가까운 노드부터 차례대로 탐색하는 방식입니다.특히 최단 거리 문제에서 매우 유용하게 사용되므로 ..