이번에는 Backtracking 다음 챕터인 DFS 와 BFS 를 다 끝냈다. DFS 는 Backtracking 과 같이 재귀함수를 사용하여 익숙하게 넘어간 것 같다.
하지만 BFS 가 좀 문제였는데 Backtracking 전에 있는 Simulation 챕터에 격자 쪽을 다 하고 넘어왔다면 더 쉬웠을 거란 생각이 든다.
아무튼 다했으니 다 풀긴 했지만 헷갈렸던 BFS 에 대해 설명해보려고 한다.
먼저 BFS 란 Breadth First Search 의 줄임말로 너비 우선 탐색이라고 한다.
스택처럼 동작하는 DFS 와는 다르게 BFS 는 Queue 를 사용한다.
큐는 FIFO(First In First Out) 방식을 사용하는 자료 구조이다. 즉 먼저 들어간 것이 먼저 나오는 구조이다.
이를 사용하면 하나의 노드를 기준으로 같은 거리에 있는 노드를 먼저 순회를 할 수가 있다.
위의 그래프를 통해 설명을 해보겠다.
순회 방법를 먼저 보자
먼저 루트 노드인 1 을 큐에 넣는다.
큐에 있는 1을 꺼내고 1과 연결되어 있는 노드들을 큐에 넣는다. 즉 2, 3, 4 를 넣는다.
가장 앞에 있는 2 를 꺼내고 2에 연결 되어 있는 노드 5 를 넣는다.
3 을 꺼내고 연결되어 있는 노드가 없기 때문에 넘어간다.
4 를 꺼내고 연결된 6을 넣는다.
2, 3, 4 가 모두 꺼내졌으므로 2 와 연결되었던 노드가 큐의 제일 앞에 있을 것 이므로 5 를 꺼내고 다음으로 넘어간다.
4 뒤에있던 6 을 꺼내고 6과 연결된 7을 넣는다.
7을 꺼내고 뒤의 노드가 없기 때문에 다음으로 넘어간다.
큐에 원소가 하나도 없으므로 순회를 종료한다.
BFS 는 특히 어느 지점에 도달하는 최소 거리를 구할 때 많이 사용하는 방법이다.
예를 들어보면
' 한 지점에서 출발하여 특정 지점에 도달 할 수 있지를 구하시오 ' 같은 문제가 나오면
BFS 로 구현을 하고 특정 지점에 도착했을 때 BFS 를 바로 종료하면 될 것이다. 굳이 모든 노드를 방문을 하지 않아도 되는 것이다.
BFS 는 또한 간선 사이 거리가 같다고 가정했을 때 최단 거리를 구하는 데에도 많이 쓰인다.
이게 가능한 이유는 가장 가까운 것들 부터 먼저 처리를 하기 때문이다.
위에 있던 그래프로 설명을 해보자면
1 에서는 2, 3, 4 가 연결되어 있었는데 1은 거리가 0 이라고 가정해보면
1과 연결되어 있는 2, 3, 4 는 거리가 1이다.
2 와 연결되어 있는 5, 4 와 연결되어 있는 6 은 거리가 2가 될 것이고
6과 연결되어 있는 7은 거리가 3이 될 것이다.
BFS 의 흐름과 쓰임새를 살펴봤으니 구현 방법을 설명해보도록 하겠다.
BFS 를 공부하면서 가장 중요하게 생각했던 것은 visited 배열이다. visited 배열이란 어떤 노드가 큐에 들어간 적이 있는지를 저장하는 배열이다.
이 배열이 있어야지 같은 노드를 여러번 반복해서 접근하지 않게 된다.
또 위의 그래프를 예시로 들어 말해본다면
1 과 연결된 2, 3, 4 를 큐에 넣고 2를 뺀다고 했을 때 visited 배열이 없다면 사실 2과 연결된 노드는 5만 존재하는 것이 아니라 1 과 5가 되는 것이다.
그렇기 때문에 1을 큐에 넣으면서 visited 배열에 1을 추가를 한다면 '2와 연결되어있고 visited 배열에 속하지 않은 노드' 인 5 가 다음 큐에 들어갈 수 있는 것이다.
또 BFS 를 공부하면서 중요하게 생각했던 것이 있었는데 이건 코드를 보면서 다시 살펴보겠다.
인접 행렬을 사용하는 BFS 코드
import java.util.*;
public class Main {
static boolean[][] visited;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static int result = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
grid[i][j] = sc.nextInt();
if(grid[0][0] != 1){
System.out.println(0);
return;
}
visited = new boolean[n][m];
BFS(grid);
System.out.println(result);
}
public static void BFS(int[][] grid){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
visited[0][0] = true;
while(!queue.isEmpty()){
int[] current = queue.poll();
int y = current[0];
int x = current[1];
// 이 부분
if((y == grid.length-1) && (x == grid[0].length-1)){
result = 1;
return;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
// 이 부분
if (ny >= 0 && ny < grid.length &&
nx >= 0 && nx < grid[0].length &&
grid[ny][nx] == 1 &&
!visited[ny][nx]) {
visited[ny][nx] = true;
queue.add(new int[]{ny, nx});
}
}
}
}
}
위 코드는 이차원 배열로 이루어진 격자의 마지막 칸에 도달할 수 있는지 BFS 로 탐색하는 코드이다.
보통 인접 행렬이나 인접 리스트로 BFS 를 많이 구현하는데
특히 인접 행렬을 사용했을 때 경계값을 잘 살펴보아야 한다.
예를 들어
1. 격자의 index 를 입력값에 -1 을 해야 하는 경우
2. 격자를 벗어나는 경우 ( 특히 격자의 가로 세로 길이가 다를 경우 )
3. 시작점과 끝점이 존재할 경우 예외를 처리해야 하는 경우
이런 것들이 있다. 1번과 2번은 굉장히 사소해 보이지만 코드가 길어지면 정말 찾기 힘들어지기 때문에 처음부터 생각해두는 것이 편하다.
3번도 정말 중요한데 시작점 끝점 뿐만 아니라 격자에 다른 수들을 사용해 여러 가지 디테일을 다르게 가져갔을 때 해당한다.
이 때는 큐에 넣어야 하는 노드와 넣지 말아야 하는 노드의 구분을 잘 해야 한다.
이 세 가지만 잘 생각하면서 BFS 를 푼다면 큰 사고 없이 문제가 풀릴 것이다.
벌써 코드트리 청약 챌린지 마지막 주차인데
생각보다 시간이 빨리 지나가는 것 같아 마음이 아프다.
해야할 건 산더미 같은데 시간은 한정되어 있으니... 그래도 코딩 테스트를 위해서 열심히 해봐야겠다.
블로그 글을 이 챌린지로 인해서 처음 쓰게 되었는데 생각보다 재밌고 의미있는 것 같다.
특히 생각을 생각이나 느낌을 남긴다는 것이 마음에 든다.
그냥 지나갈 수 있는 하루를 뭐라도 남긴다는 사실 자체가 위안을 준다고 해야하나
아무튼 코드트리 챌린지는 이번으로 마무리지만 코딩테스트 공부 관련해서 글은 계속 적어야겠다.
혹시나 이 글을 보는 사람이 있다면 또 코딩 테스트에 관해 고민을 가지고 있다면 코드트리에 한 번 들어가보는 것을 추천해주고 싶다.
Codetree: Master Coding Interviews - Data Structures & Algorithms
Master algorithms, ace tech interviews, and elevate your coding skills with Codetree's systematic curriculum and expert-crafted problem sets.
www.codetree.ai