BFS 는 그래프 탐색 방법 중 하나다
그래프 탐색
어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을때, 시작점에서
간선을 타고 이동할 수 있는정점들을 모두 찾아야 하는 문제
- 하나의 정점에서 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것
- 노드는 딱 한 번씩만 방문
2가지 방법이 있는데 오늘은 그 중에서 BFS에 대해서 알아보자!
BFS(Breadth-First Search)
너비우선 탐색으로, 시작 노드로부터 자식 노드들을 순서대로 탐색하면서 너비를 우선으로 탐색하는 그래프 탐색 방법
완전탐색 알고리즘에 속함
가중치가 없는 그래프에서 같은 거리에 있는 모든 노드를 탐색한 후, 다음 거리의 노드를 탐색하기 시작하는 방식으로 진행
Queue를 활용해 다음 방문할 노드를 추적
동작 과정
- 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리
- 2번 의 과정을 반복
- 방문 처리 : 탐색한 노드를 재방문하지 않도록 구분 → 큐에 한번이라도 들어간 노드를 다시 삽입하지 않도록 체크
어 이걸 gif로 표현하고 싶지만 만드는 방법을 모르니 패스해야겟다
이 블로그에 있는 gif가 잘 표현하고 있는 것 같아 링크 달아놓습니다
장점
- 간단하고 이해가 쉬움
- 연결된 구성 요소에서 모든 노드를 찾는 데 사용
단점
- 많은 메모리가 필요해서 큰 그래프에는 적합하지 않음
- 그래프를 순회할 때 가중치를 고려 X, 가중치 간선이 있는 그래프에는 적합 X
- 다음 깊이로 이동하기 전에 노드의 모든 하위 항목을 탐색하기 때문에 분기가 많은 그래프에는 비효율적
- 다음 깊이로 이동하기 전에 현재 깊이의 모든 노드를 방문해서 노드 수가 많은 그래프에는 비효율적
- 목표 노드가 시작 노드에서 멀면 다음 깊이로 이동하기 전에 주어진 모든 깊이의 노드를 탐색해서 비효율적
단점이 더 많은데..
일단 지금까지 이해한 바로는 시작노드에서 출발해서 큐에 넣고 시작한다
그 후에 큐에서 노드를 빼면서 인접 노드를 큐에 저장하고 빠진 큐들은 방문 노드에 저장을 한다
모든 노드를 방문할 때까지 반복하면 되는 것 같다
이제 이론은 대충 알았으니 문제를 한 번 풀어보자!
백준 7569 토마토
오늘의 문제는 백준 골드 5 문제다..
문제의 이름이 토마토다
나는 방울토마토는 좋아하는데, 토마토는 별로 좋아하지 않는다
아 카프레제에 있는 토마토는 좋아한다
아무튼 문제를 한 번 살펴보자
문제 설명
- 격자 모양 상자, 수직으로 쌓음
- 익은 토마토와 인접한 토마토들은 하루가 지나면 익음
- 저절로 익는 경우 X
- 대각선 영향 X → 위, 아래, 오른쪽, 왼쪽, 앞, 뒤
- 며칠이 지나면 다 익는지
요약하자면 이렇다
전염성으로 익는 토마토들이다
입력은 문제 그대로 입력된다
상자크기 M(가로) x N(세로), 상자 높이 H
가장 밑의 상자부터 주어짐
1 : 익은 토마토
0 : 안익은 토마토
-1 : 토마토 없음
출력
토마토가 모두 익지 못하면 -1 반환
그 외 최소 횟수 반환
풀이
문제 설명은 이 정도면 됐고 이제 문제를 한 번 풀어보자
전염성으로 퍼지는 토마토들이라서 BFS 를 사용하면 될 것 같다
내가 생각한 방식은 이렇다
- 초기 1인 토마토들의 좌표를
queue에 넣음queue에서 하나씩 빼면서 근처에 있는 토마토들을 1로 변경 후 해당 좌표를 다시 큐에 넣음
- -1이면 패스
queue가 바닥날때까지 반복queue에 아뭇것도 없을때, 상자에 0이 있으면 -1 출력
이렇게 하면 풀수 있을것 같았고 풀어봤다!
일단 경계값이나, 다른 조건들도 있는데 고건 코드에서 설명하겠따
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[][][] tomatoes = new int[H][N][M];
Queue<List<Integer>> queue = new LinkedList();
int count = -1;
for (int i = 0; i < H; i++) { // 토마토 상자 저장
for (int j = 0; j < N; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < M; k++) {
int tomato = Integer.parseInt(st.nextToken());
tomatoes[i][j][k] = tomato;
if (tomato == 1) {
queue.add(List.of(i, j, k));
}
}
}
}
while (!queue.isEmpty()) { // 큐가 바닥날때까지 반복
int size = queue.size(); // 한번 전염될때의 사이즈 저장
for (int s = 0; s < size; s++) { // 큐의 사이즈만큼 반복 - 전염
List<Integer> temp = queue.poll();
if (tomatoes[temp.get(0)][temp.get(1)][temp.get(2)] == 1) {
if (temp.get(0) + 1 < H && tomatoes[temp.get(0) + 1][temp.get(1)][temp.get(2)] == 0) {
tomatoes[temp.get(0) + 1][temp.get(1)][temp.get(2)] = 1;
queue.add(List.of(temp.get(0) + 1, temp.get(1), temp.get(2)));
}
if (temp.get(0) - 1 >= 0 && tomatoes[temp.get(0) - 1][temp.get(1)][temp.get(2)] == 0) {
tomatoes[temp.get(0) - 1][temp.get(1)][temp.get(2)] = 1;
queue.add(List.of(temp.get(0) - 1, temp.get(1), temp.get(2)));
}
if (temp.get(1) + 1 < N && tomatoes[temp.get(0)][temp.get(1) + 1][temp.get(2)] == 0) {
tomatoes[temp.get(0)][temp.get(1) + 1][temp.get(2)] = 1;
queue.add(List.of(temp.get(0), temp.get(1) + 1, temp.get(2)));
}
if (temp.get(1) - 1 >= 0 && tomatoes[temp.get(0)][temp.get(1) - 1][temp.get(2)] == 0) {
tomatoes[temp.get(0)][temp.get(1) - 1][temp.get(2)] = 1;
queue.add(List.of(temp.get(0), temp.get(1) - 1, temp.get(2)));
}
if (temp.get(2) + 1 < M && tomatoes[temp.get(0)][temp.get(1)][temp.get(2) + 1] == 0) {
tomatoes[temp.get(0)][temp.get(1)][temp.get(2) + 1] = 1;
queue.add(List.of(temp.get(0), temp.get(1), temp.get(2) + 1));
}
if (temp.get(2) - 1 >= 0 && tomatoes[temp.get(0)][temp.get(1)][temp.get(2) - 1] == 0) {
tomatoes[temp.get(0)][temp.get(1)][temp.get(2) - 1] = 1;
queue.add(List.of(temp.get(0), temp.get(1), temp.get(2) - 1));
}
}
}
count++;
}
for (int i = 0; i < H; i++) { // 0이 있으면 -1 반환
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
if (tomatoes[i][j][k] == 0) {
System.out.println("-1");
return;
}
}
}
}
System.out.println(count);
}코드 구성이나 최적화 같은거 신경안쓰고 일단 냅다 풀어봤다
그래서 그런지 코드가 굉장히 더럽다!
우선 보면 토마토들을 입력 받아서 3차원 배열에 저장한다
그리고 큐가 빌때까지 반복을 시킨다
처음에는 count를 반복될때마다 증가시켰더니 날별로 증가하는게 아니고 그냥 queue의 사이즈만큼 증가해서 방식을 변경해줬다
전염 부분에서는 6방향을 훑으면서 1로 바꿔준다
이 부분의 코드가 굉장히 더러운데 좀 예쁘게 바꿔줘야할 것 같다
마지막은 아직 안익은 토마토가 있으면(상자에서 0이 있으면) -1을 출력하고 그게 아니라면 count를 출력해주는 부분이다
리팩토링
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[][][] tomatoes = new int[H][N][M];
Queue<int[]> queue = new LinkedList<>();
int count = -1;
for (int i = 0; i < H; i++) {
for (int j = 0; j < N; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < M; k++) {
int tomato = Integer.parseInt(st.nextToken());
tomatoes[i][j][k] = tomato;
if (tomato == 1) {
queue.add(new int[]{i, j, k});
}
}
}
}
int[][] directions = {
{1, 0, 0}, {-1, 0, 0}, {0, 1, 0},
{0, -1, 0}, {0, 0, 1}, {0, 0, -1}
};
while (!queue.isEmpty()) {
int size = queue.size();
for (int s = 0; s < size; s++) {
int[] temp = queue.poll();
int h = temp[0];
int n = temp[1];
int m = temp[2];
for (int[] dir : directions) {
int nh = h + dir[0];
int nn = n + dir[1];
int nm = m + dir[2];
if (nh >= 0 && nh < H && nn >= 0 && nn < N && nm >= 0 && nm < M) {
if (tomatoes[nh][nn][nm] == 0) {
tomatoes[nh][nn][nm] = 1;
queue.add(new int[]{nh, nn, nm});
}
}
}
}
count++;
}
// 모든 토마토가 익었는지 확인
for (int i = 0; i < H; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
if (tomatoes[i][j][k] == 0) {
System.out.println("-1");
return;
}
}
}
}
System.out.println(count);
}변경한 코드는 이렇다!
기존 코드는 이미 1인 부분까지 다시 1로 덮어 씌웠는데 그 부분을 해결했고, 반복되는 방향 확인 부분을 배열로 저장해서 처리해줬다
그랬더니 요만큼 개선됐다
후기
여전히 알고리즘은 어렵다
