4-4. BFS

BFS

• BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다.
• 모든 가중치가 1일 때, BFS는 최단거리를 구하는 알고리즘이 된다. BFS를 이용해서 최단거리를 구하기 위해서는, 다음과 같은 유형의 문제여야 한다.
  • 최소 비용 문제여야 한다.
  • 모든 간선의 가중치는 1이어야한다.
  • 정점과 간선의 갯수에 제한이 있어야 한다. 다시 말하면, 문제에서 주어진 시간 및 메모리 제한을 만족시킬 수 있어야 한다.
• 간선을 이용했을 때 이동할 수 있는 가짓수가 다른 경우, 다른 정점이라고 봐야 한다. 이런 경우에는 그래프를 쪼개서 생각해봐야 한다는 점을 주의하자.

2178 미로 탐색, 백준 온라인 저지

• (1, 1)에서 (N, M)으로 가는 가장 빠른 길을 구하는 문제이다.
• DFS 탐색으로는 문제를 풀 수 없다는 점에 주의하자. 즉, BFS 탐색을 사용해야 한다.

7576 토마토, 백준 온라인 저지

• 하루가 지나면 익은 토마토와 인접한, 익지 않은 토마토들이 익게 된다. 상자안에 익은 토마토와 익지 않은 토마토가 주어졌을 때, 토마토가 모두 익을 때까지 며칠이 소요되는지 구하는 문제이다. 단, 토마토가 저절로 익는 경우는 없다.

1697 숨바꼭질, 백준 온라인 저지

• 수빈이의 위치를 N이라고 하고 동생의 위치를 K라고 할 때, 동생을 찾는 가장 빠른 시간을 구하는 문제이다. 단, 수빈이는 N-1, N+1, N*2로 이동이 가능하다.
• 큐에 수빈이의 위치를 넣어가면서 이동시킨다. 한 번 방문한 곳은 다시 방문하지 않는 것이 좋으므로, 배열을 이용해서 체크하도록 하자.

14226 이모티콘, 백준 온라인 저지

• 화면에 이모티콘은 1개 존재한다. 이 때, 할 수 있는 연산은 다음과 같다.
  • 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  • 클립보드에 있는 모든 이모티콘을 화면에 붙여넣는다.
  • 화면에 있는 이모티콘 중 하나를 삭제한다.
• S개의 이모티콘을 만드는 데 걸리는 시간의 최소값을 구하는 문제이다.
• 하나의 정점이 서로 다른 두 개의 정보를 저장하고 있으면 안된다. 클립보드에 있는 이모티콘의 갯수에 따라서, 클립보드에 있는 이모티콘을 화면에 붙여넣는 연산의 결과가 다르다. 즉, 화면의 이모티콘 갯수 S와 클립보드에 있는 이모티콘의 갯수 C가 중요하다.