BFS는 DFS와 마찬가지로, 컴포넌트의 모든 정점을 한번씩 순회하는 용도
-> 둘다 컴포넌트의 갯수를 세거나, 각 컴포넌트의 크기를 구하는데 사용 가능
DFS는 깊이를 중시한것에 반해 BFS는 넓이 중시
-> DFS는 한 우물만 계속 파다가 끝을 보고 나서야 다른 곳으로 옮기는데 반해, BFS는 몯느 곳을 똑같이 조금씩 팜
위 그림을 예시로 들었을때 k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k인 경우
-> 위의 경우는 3단계이므로 최단 거리(필요한 최소 개수의 간선)가 3
DFS와 마찬가지로 BFS 또한, 인접리스트를 사용하였을 때 시간복잡도가 O(V+E)임
탐색은 하되 각 정점의 최단거리를 재야할 때 요긴하게 쓰임
문제 1(미로탐색) - 실버 1
https://www.acmicpc.net/problem/2178
저번에 풀어봤던 문제인데 다시 풀려했을때 헷갈렸다!
문제 2(트리의 지름 구하기) - 골드2(Hard)
트리의 지름이랑 임의의 두 노드 사이에 거리 중 가장 먼 거리!
-> 이 문제는 꼭한번 다시 풀어보자!, 로직은 이해할만함
문제 3(촌수 계산) - 실버2
https://www.acmicpc.net/problem/2644
적당히 할만하다!, 거리를 어떻게 다룰지를 잘 생각해보자!
문제 4(나이트의 이동) - 실버1
https://www.acmicpc.net/problem/7562
어떻게 하다보니.. 잘 맞췄다...
-> 앞으로 위치를 나타낼때 point라는 새로운 클래스를 생성하여 코드를 깔끔하게 해보자~
문제 5(상범 빌딩) - 골드 5
https://www.acmicpc.net/problem/6593
솔직히 로직은 그렇게 어렵진 않았는데... 삼차원 배열과 좌표를 다룰려니 좀 힘들었따!
문제 6(스타트 링크) - 실버 1
https://www.acmicpc.net/problem/5014
처음 코드를 짰을 때 시작하는 지점과 도착하는 지점이 같을때 use the stairs가 떴다..
-> 문제를 잘읽어보고 로직을 짜자! 쉬운 문제이긴 했음
문제 7(불) - 골드 4(Hard)
https://www.acmicpc.net/problem/5427
우선 사람과 불을 시간개념을 적용시켜야 하고, 각각에 대한 스택을 두어 bfs 시켜야함
(어렵다..)
문제 8(토마토) - 골드 5
https://www.acmicpc.net/problem/7569
아이디어 잘 캐치하기
내가 푼 방법과 조금 다른 코드 일부
public static void bfs(Queue<Tomato> queue) {
while (!queue.isEmpty()) {
Tomato current = queue.poll();
int x = current.x;
int y = current.y;
int z = current.z;
for (int i = 0; i < 6; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
int nz = z + dz[i];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < h && ny < n && nz < m) {
if (tomatoes[nx][ny][nz] == 0 && !visited[nx][ny][nz]) {
visited[nx][ny][nz] = true;
tomatoes[nx][ny][nz] = tomatoes[x][y][z] + 1;
queue.offer(new Tomato(nx, ny, nz));
}
}
}
}
}
public static int solve() {
Queue<Tomato> queue = new LinkedList<>();
for (int x = 0; x < h; x++) {
for (int y = 0; y < n; y++) {
for (int z = 0; z < m; z++) {
if (tomatoes[x][y][z] == 1 && !visited[x][y][z]) {
visited[x][y][z] = true;
queue.offer(new Tomato(x, y, z));
}
}
}
}
bfs(queue);
int maxDay = -1;
for (int x = 0; x < h; x++) {
for (int y = 0; y < n; y++) {
for (int z = 0; z < m; z++) {
if (tomatoes[x][y][z] == 0) {
return -1;
}
maxDay = Math.max(maxDay, tomatoes[x][y][z]);
}
}
}
return maxDay - 1;
}문제 9(숨바꼭질) - 실버1
https://www.acmicpc.net/problem/1697
그냥 적당한 문제
public class Main {
static int n, k;
static boolean[] visited;
public static int bfs() {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{n, 0});
visited[n] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int position = current[0];
int time = current[1];
if (position == k) {
return time;
}
int[] nextPositions = {position - 1, position + 1, position * 2};
for (int next : nextPositions) {
if (next >= 0 && next <= 100000 && !visited[next]) {
visited[next] = true;
queue.offer(new int[]{next, time + 1});
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
visited = new boolean[100001];
int result = bfs();
System.out.println(result);
}
}배열 크기만 잘 잡으면 됨!
다음에 풀어볼 문제
