동까의 코딩

1. BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.BFS(너비 우선 탐색)는 그래프나 트리에서 시작 정점에서부터 인접한 노드를 먼저 방문하는 알고리즘입니다. BFS의 핵심 아이디어는 시작 정점으로부터 거리가 가까운 노드들을 먼저 처리하고, 그 다음 거리에 있는 노드들을 차례대로 탐색하는 것입니다.먼저 BFS의 작동 원리를 정리하면 다음과 같습니다.시작 정점 선택: 탐색의 출발점이 되는 정점을 선택합니다.큐(Queue) 사용: BFS에서는 FIFO(First-In, First-Out) 원칙을 따르는 큐를 사용합니다. 즉, 먼저 방문한 정점부터 처리하게 되어, 각 단계별(레벨별)로 노드를 확장합니다.인접 노드 방문: 현재 정점..

파이썬 프로그래머스 - 게임 맵 최단거리문제 설명프로그래머스의 게임 맵 최단거리 문제는 직사각형 모양의 맵에서 시작점(0, 0)에서 도착점(n-1, m-1)까지 이동할 때 거쳐야 하는 최소 칸 수를 구하는 문제입니다.맵은 1과 0으로 구성되며, 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타냅니다.상하좌우 방향으로만 이동할 수 있으며, 시작점과 도착점은 항상 1입니다.문제 접근 방식BFS(너비 우선 탐색) 활용시작점에서 출발하여 도착점까지 도달하는 경로 중, 가장 짧은 경로를 찾아내기 위해 BFS를 사용합니다.방문 처리방문한 칸을 추적하여 중복 방문을 방지합니다.거리 기록현재까지 이동한 거리를 maps 배열에 기록하여, 각 칸에 도달하는 데 필요한 최소 이동 횟수를 저장합니다.종료 조건도착점에..