너비우선 탐색 vs 깊이우선 탐색 수도 코드

깊이우선 탐색 (DFS)

개념

1. Stack 사용 / 재귀
2. 깊이 우선 탐색
3. 탐색할 때 마다 조건을 주는 경우에 유리 (백트래킹)
4. 수도 코드

1. 체크인
2. 목적지인가?
3. 인접한 곳 탐색
4. 갈 수 있는가?
   4-1. 간다.
5. 체크아웃

 

구현

static final int[] dr = {0, -1, 0, 1};
static final int[] dc = {-1, 0, 1, 0};
static int N;
static int endR, endC;
static boolean[][] visited;

public static void dfs(int r, int c) {
    // 1. 체크인
    visited[r][c] = true;

    // 2. 목적지인가?
    if (r == endR && c == endC) {
        //Do something
        return;
    }

    // 3. 인접한 곳 탐색
    for (int i = 0; i < 4; i++) {
        int newR = r + dr[i];
        int newC = c + dc[i];

        // 4. 갈 수 있는가?
        if (0 <= newR && newR < N && 0 <= newC && newC < N) {
            if (visited[newR][newC] == false) {
                // 4-1. 간다.
                dfs(newR, newC);
            }
        }
    }
    
    // 5. 체크아웃
    visited[r][c] = false;
}

1. 체크인
   • 해당 노드를 탐색하고 있다는 것을 표현 → 이렇게 표현해서 다음 depth를 향해 재귀 함수가 호출됐을 때, 이미 탐색 된 노드라는 것을 표현해줌

   visited[r][c] = true;
   

2. 목적지인가?
   • 기저조건. 종료되기 위한 조건을 작성함 ⇒ 문제에 따라 없는 경우도 있음 (이럴 땐 주로 모든 탐색이 끝났을 때 == 갈 곳이 없을 때)

   if (r == endR && c == endC) {
       //Do something
       return;
   }
   

3. 인접한 곳 탐색
   • 배열은 4방 탐색, 8방 탐색 : 문제에 따라 다름
   • 그래프는 인접 리스트 방식 탐색

   for (int i = 0; i < 4; i++) {
   	  int newR = r + dr[i];
       int newC = c + dc[i];
   

4. 갈 수 있는가?
   • 문제에서 정한 조건에 부합해서 다음 탐색이 가능한가. 문제에 따라 다름 → 이 부분을 잘 작성해야 함. 아래의 2개는 배열 dfs에서 주로 사용되는 기준
     • 범위 내에 있는가?
     • 이미 탐색한 노드인가

   if (0 <= newR && newR < N && 0 <= newC && newC < N) {
       if (visited[newR][newC] == false) {
   

   1. 간다
      • 재귀로 다음 depth로 간다.

      dfs(newR, newC);
      

5. 체크아웃
   • 이미 탐색이 완료됐다는 의미로 vistied 를 원래대로 돌려둔다.

   visited[r][c] = false;
   

 

 

 

너비우선 탐색 (BFS)

개념

1. Queue 사용
2. 너비 우선 탐색
3. 모든 경우를 탐색하고 싶을 때 유리
4. 수도 코드

0. 초기세팅
1. 큐에서 꺼내옴
2. 목적지인가?
3. 인접한 곳 탐색
4. 갈 수 있는가?
   4-1. 체크인
   4-2. 큐에 넣는다.

구현

static final int[] dr = {0, -1, 0, 1};
static final int[] dc = {-1, 0, 1, 0};
static int N;
static int endR, endC;
static boolean[][] visited;

public static void bfs(int r, int c) {
    // 0. 초기 세팅
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[] {r, c});
    visited[r][c] = true;

    while (! q.isEmpty()) {
        // 1. 큐에서 꺼내옴
        int[] current = q.poll();

        // 2. 목적지인가?
        if (current[0] == endR && current[1] == endC) {
            //Do something
            return;
        }

        // 3. 인접한 곳 탐색
        for (int i = 0; i < N; i++) {
            int newR = r + dr[i];
            int newC = c + dc[i];
            
            // 4. 갈 수 있는가?
            if (0 <= newR && newR < N && 0 <= newC && newC < N) {
                if (visited[newR][newC] == false) {
                    // 4-1. 체크인
                    visited[newR][newC] = true;
                    // 4-2. 큐에 넣는다.
                    q.add(new int[] {newR, newC});
                }
            }
        }
    }
}

1. 초기세팅
   • 큐 자료구조 만들고
   • 시작점을 큐에다가 넣음

   Queue<int[]> q = new LinkedList<>();
   q.add(new int[] {r, c});
   visited[r][c] = true;
   

2. 큐에서 꺼내옴
   • 큐가 빌 때 까지 돌면서 (더 이상 탐색할 곳이 없을 때 까지)
   • 하나씩 꺼냄

   int[] current = q.poll();
   

3. 목적지인가?
   • 꺼낸 곳이 목적지인지 확인
   • 문제에 따라 없는 경우도 있음 (이럴 땐 주로 모든 탐색이 끝났을 때 == 갈 곳이 없을 때)

   if (current[0] == endR && current[1] == endC) {
       //Do something
       return;
   }
   

4. 인접한 곳 탐색
   • 배열은 4방 탐색, 8방 탐색 : 문제에 따라 다름
   • 그래프는 인접 리스트 방식 탐색

   for (int i = 0; i < N; i++) {
       int newR = r + dr[i];
       int newC = c + dc[i];
   

5. 갈 수 있는가?
   • 문제에서 정한 조건에 부합해서 다음 탐색이 가능한가. 문제에 따라 다름 → 이 부분을 잘 작성해야 함. 아래의 2개는 배열 bfs에서 주로 사용되는 기준
     • 범위 내에 있는가?
     • 이미 탐색한 노드인가

   if (0 <= newR && newR < N && 0 <= newC && newC < N) {
       if (visited[newR][newC] == false) {
   

   1. 체크인
      • 큐에다가 넣는다고 체크한다. 이를 체크해서 다른 노드로부터 같은 노드가 불리더라도 이미 체크되었다고 판단하여 큐에 중복으로 넣지 않는다.

      visited[newR][newC] = true;
      

   2. 큐에 넣음
      • 큐에 넣음 == 다음에 순서에 맞게 탐색하겠다고 기록해둠

      q.add(new int[] {newR, newC});