BFS2

• [백준]3197 백조의 호수 3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있.. TIL/SW&백준 문제 리뷰 2022. 7. 31.

• 

  210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS, Breadth - First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 즉 깊게 보다 넓게를 우선시한 탐색 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 활용함 BFS의 과정 시작 정점 방문 깊이 1인 모든 노드 방문 깊이 2인 모든 노드 방문.... (반복) 더 이상 방문할 곳 없으면 탐색 마침 노드 방문 세부 과정은 (큐에서 꺼낸) 노드를 방문하였을 경우 큐에서 꺼낸 노드 방문 큐에서 꺼낸 노드와 인접한 노드들 모두 방문 방문한 노드들 큐에 삽입, 더 이상 없다면 큐에서 노드 꺼냄 이런 과정을 반복한다 예시 시간복잡도 : 인접 행렬 사용시 : O(노드수 +간선수) 인접 리스트 사용시 : O(노드수^2) 깊이 우선 탐색(DFS, Dep.. 미가공 필기(알고리즘) 2021. 7. 9.