요르딩딩

CHAPTER 3. DFS/BFS 본문

[코딩테스트]/이론

CHAPTER 3. DFS/BFS

요르딩딩 2022. 2. 10. 17:00
728x90
반응형

DFS

  • (Depth-First Search) : 깊이 우선 탐색
  • 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
  • 동작원리 : 스택 자료구조에 기초한다.
  • 구현방법 : 재귀함수 이용
  • 시간복잡도 :O(N)
import java.util.*;

public class Main {
	public static boolean[] visited_Node = new boolean[7]; 	// 방문했던 노드를 체크하기 위한 변수
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); // 그래프 변수

	// 같은 Depth가 있을 경우, 작은 숫자를 먼저 방문(add를 작은 숫자 먼저 했기 때문)
    public static void dfs(int num) {
    	visited_Node[num] = true; // 현재 노드를 방문 처리
        System.out.print(num + " ");
        
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(num).size(); i++) {
            int temp = graph.get(num).get(i);
            if (!visited_Node[temp]) 
            	dfs(temp);
        }
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < 7; i++) {         // 그래프에 7개의 노드 추가
            graph.add(new ArrayList<Integer>());
        }

        // 노드에 연결된 노드 정보 저장 
        graph.get(0).add(1);
        graph.get(0).add(2);
        
        graph.get(1).add(0);
        graph.get(1).add(5);
        
        graph.get(2).add(0);
        graph.get(2).add(3);
        
        graph.get(3).add(2);
        graph.get(3).add(4);
        graph.get(3).add(6);
        
        graph.get(4).add(3);

        graph.get(5).add(1);

        graph.get(6).add(3);

        dfs(0); //첫노드
    }
}

//결과 : 0 1 5 2 3 4 6

 

BFS

  • Breadth-First Search) : 너비 우선 탐색
  • 그래프에서 가까운 노드부터 탐색하는 알고리즘이며, 아래 예제에서는 선입선출의 특성을 가진 큐(Queue)를 이용한다.
  • 동작원리 : 큐 자료구조에 기초한다.
  • 구현방법 : 큐 이용
  • 시간복잡도 :O(N), (DFS보다 빠름)
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static boolean[] visited_Node = new boolean[7]; 	// 방문했던 노드를 체크하기 위한 변수
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();// 그래프 변수
	public static ArrayList<Integer> result = new ArrayList<Integer>();

	// 가까이 있는 원소부터 탐색
    public static void bfs(int num) {
    	Queue<Integer> q = new LinkedList<>();
    	
        q.offer(num);
    	visited_Node[num] = true; // 1.현재 노드를 방문 처리
        
    	while(!q.isEmpty()) {
            int now = q.poll();  // queue에서 하나의 원소를 뽑음, 선입선출이기에 먼저 들어온 것이 먼저 뽑힘
            
            result.add(now); // 결과저장
            
            // 해당 원소와 연결되어 있는 원소 확인
            for(int i = 0; i < graph.get(now).size(); i++) {
                int temp = graph.get(now).get(i);
                
                if(!visited_Node[temp]) { // 아직 방문처리가 안 된 원소는 queue에 넣고 방문 처리
                	q.offer(temp);
                	visited_Node[temp] = true; // 2.방문 처리
                }
            }
        }
        
        for(int i=0; i< result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
    
	public static void main(String[] args) {
        for (int i = 0; i < 7; i++) { // 그래프에 7개의 노드 추가
            graph.add(new ArrayList<Integer>());
        }

        // 노드에 연결된 노드 정보 저장 
        graph.get(0).add(1);
        graph.get(0).add(2);

        graph.get(1).add(0);
        graph.get(1).add(5);

        graph.get(2).add(0);
        graph.get(2).add(3);

        graph.get(3).add(2);
        graph.get(3).add(4);
        graph.get(3).add(6);
 
        graph.get(4).add(3);

        graph.get(5).add(1);

        graph.get(6).add(3);
        
        bfs(0);
	}
}
//결과 : 0 1 2 5 3 4 6

 

참고 : https://ajdahrdl.tistory.com/96?category=985353 

 

문제 

DFS(행렬) - 음료수 얼려먹기

import java.util.*;

public class Main {

    public static int n, m;
    public static int[][] graph = new int[1000][1000];

    // DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
    public static boolean dfs(int x, int y) {
        // 주어진 범위를 벗어나는 경우에는 즉시 종료
        if (x <= -1 || x >=n || y <= -1 || y >= m) {
            return false;
        }
        // 현재 노드를 아직 방문하지 않았다면
        if (graph[x][y] == 0) {
            // 해당 노드 방문 처리
            graph[x][y] = 1;
            // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        // 모든 노드(위치)에 대하여 음료수 채우기
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 현재 위치에서 DFS 수행
                if (dfs(i, j)) {
                    result += 1;
                }
            }
        }
        System.out.println(result); // 정답 출력 
    }

}

BFS(행렬) - 미로탈출

import java.util.*;

class Node {

    private int x;
    private int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
}

public class Main {

    public static int n, m;
    public static int[][] graph = new int[201][201];

    // 이동할 네 가지 방향 정의 (상, 하, 좌, 우) 
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};

    public static int bfs(int x, int y) {
        // 큐(Queue) 구현을 위해 queue 라이브러리 사용 
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        // 큐가 빌 때까지 반복하기 
        while(!q.isEmpty()) {
            Node node = q.poll();
            x = node.getX();
            y = node.getY();
            // 현재 위치에서 4가지 방향으로의 위치 확인
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 미로 찾기 공간을 벗어난 경우 무시
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                // 벽인 경우 무시
                if (graph[nx][ny] == 0) continue;
                // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Node(nx, ny));
                } 
            } 
        }
        // 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n - 1][m - 1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        // BFS를 수행한 결과 출력
        System.out.println(bfs(0, 0));
    }

}

로직 암기

No DFS/리스트  DFS/행렬 
  boolean[] visited
ArrayList graph
ArrayList result		 int[][] graph
int[] dx/dy
1 void dfs(int now) boolean dfs(int x, int y)
2 방문처리 .
3 reulst.add .
4 for(size) //종료조건 범위, 거짓 //종료조건
5 아직 방문전 아직 방문전
6 . 방문처리
7 재귀 재귀 (상하좌우), 참
No BFS/리스트  BFS/행렬 
  boolean[] visited
ArrayList graph
ArrayList result		 class Node
int[][] graph
int[] dx/dy
1 . Class Node
2 void bfs(int now) int bfs (int x int y)
3 큐, 삽입 큐, 삽입
4 방문처리 .
5 while(!q.isEmpty()) while(!q.isEmpty())
6 poll poll
7 result.add .
8 for(size()) for(상하좌우)
9 . 범위, 방문했다면 continue/ 방문했다면 continue
10 아직 방문전 아직 방문전
11 삽입 삽입
12 방문처리 방문처리

 

728x90
반응형

'[코딩테스트] > 이론' 카테고리의 다른 글

다이나믹 프로그래밍  (0) 2022.02.22
Chapter 9. 최단경로  (0) 2022.02.14
CHAPTER 4. 정렬  (0) 2022.02.03
CHAPTER 8. 그래프 이론  (0) 2022.01.20
플로이드 워셜 알고리즘  (0) 2022.01.17
'[코딩테스트]/이론' Related Articles more
Comments