Cloud.log

[BOJ] 2178. 미로 탐색 (Python/BFS/Silver 1)

[Baekjoon] 2178. 미로 탐색Silver 1 | #BFS #최단경로문제 바로가기 🔗1. 문제 요약 및 풀이 방식(1, 1)에서 출발하여 (N, M) 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.최단 거리 = BFS: 모든 간선의 가중치가 동일할 때 최단 경로를 보장하는 BFS를 사용한다.거리 업데이트: 다음 칸으로 이동할 때 현재 칸의 값 + 1을 저장하여 방문 여부와 거리를 동시에 관리한다.2. 전체 코드 (Python)import sysfrom collections import dequeinput = sys.stdin.readline# 데이터 입력 시 미리 int형 리스트로 변환 (최적화)N, M = map(int, input().split())graph = [list(..

[Baekjoon] 11724. 연결 요소의 개수Silver 2 | #DFS #BFS #그래프이론문제 바로가기 🔗1. 문제 요약 및 접근 방식방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 문제이다. 즉, 그래프가 몇 개의 독립된 덩어리로 나뉘어 있는지 찾아야 한다.정점 중심 탐색: 간선이 없는 고립된 정점도 하나의 연결 요소로 취급해야 하므로, 모든 정점(1~N)을 순회하며 방문 체크를 해야 한다.인접 리스트 활용: 특정 정점과 연결된 노드들만 효율적으로 탐색하기 위해 인접 행렬보다 인접 리스트를 사용한다.무방향성: 양방향 연결을 위해 graph[u].append(v)와 graph[v].append(u)를 모두 수행한다.2. 전체 코드 (Python ..

그래프 탐색(Graph Search) 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다. 단순히 그래프의 노드를 탐색하는 것으로 문제를 해결한다. 그래프 탐색에는 BFS/DFS가 있다. ✔ BFS(Breadth First Search) 정의 너비 우선 탐색이라는 뜻이고, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 아래의 그림을 보면서 쉽게 이해해보자. 위의 그림과 같이 6개의 노드와 5개의 간선(노드의 개수-1)이 있다. 노드 1번부터 시작해서 2번을 탐색하고 다음으로 4번 노드를 탐색하는 게 아닌 3번 먼저 탐색하는 것이다. 3번 옆에 아무것도 없으므로 다시 2번 노드로 돌아와서 2번 노드의 하위 노드 중 하나인 4번을 탐색한다. 4번을 끝냈으면 다..