그래프 탐색

Joo·2022년 9월 14일

알고리즘

목록 보기

1/9

1. 그래프

정점(vertex) + 간선(edge)
간선
- 무방향 or 방향
- 가중치 유무

방향 o, 가중치 o

차수
- deg(x)
  - x의 차수
  - x와 연결된 간선의 수
모든 정점의 차수의 합
- 간선의 개수 x 2 → 그려보면 앎
그래프를 저장하는 방법
1. 인접 행렬
2. 인접 리스트

인접 행렬 (Adjacency Matrix)

2차원 배열을 사용해 저장

int[][] adjacencyMatrix = int new[vertex][vertex];

공간 복잡도 : O(V^2)
- 메모리를 너무 많이 차지함
  - 정점이 많아지면 사용 못함 ex) V = 10만 → V^2 = 100억
시간 복잡도
- A ↔ B 이동 가능? (무방향)
  - O(1) → adj[A][B]만 확인하면 됨
- 정점 A에서 갈 수 있는 정점은?
  - O(V) → 모든 정점 확인해봐야함

인접 리스트 (Adjacency List)

2차원 ArrayList를 사용해 저장

ArrayList<ArrayList<Integer>> adjacencyList;

or

ArrayList<Integer>[] adjacencyList; // 이게 쓰기 더 편한듯

공간 복잡도 : O(E)
- 모든 정점의 차수합만큼 필요
  - 간선(E) x 2 = O(2E) = O(E)
시간 복잡도
- A ↔ B 이동 가능?
  - O(min(deg(A),deg(B))) → A,B 둘 중 차수 낮은 것에 따라 결정
- 정점 A에서 갈 수 있는 정점은?
  - O(deg(A)) → A와 연결된 정점만큼 조회

인접 행렬 vs 인접 리스트

A,B가 연결되어있는지 아닌지 여부만 궁금 → 인접 행렬 사용
그것 아니면 인접 리스트 사용 → 인접 리스트를 더 많이 씀

탐색 (Search)

시작점에서 간선을 0개 이상 사용하여 갈 수 있는 모든 정점들을 찾는 것

정점, 간선, 시작점 주어짐
visit 배열, 인접 행렬 or 인접 리스트 변수 필요
dfs, bfs 둘 다 한번 메소드가 실행되면 방문할 수 있는 정점을 모두 탐색함
- 탐색 작업을 몇번할 지 잘 생각하면서 문제 풀 것
- dfs 내부 재귀는 별개로 생각

그래프의 연결 기준이 방향으로 주어지는 경우

보통 2차원 정점
- x, y
- 2차원 정점은 bfs보다 dfs로 하는게 더 편한듯
  - bfs는 큐에 x,y 좌표에 대한 값을 저장하고 있어야 함
  - dfs는 x,y 좌표를 매개변수로 넘겨주기만 하면 됨
갈 수 있는 방향이 주어짐
- 좌우, 위아래, 대각선
- 갈 수 방향에 정점이 있는지 확인하여 연결 여부 확인
  - 이 때 연결된 정점의 정보를 저장해야하면 인접 행렬,리스트에 저장
  - 저장할 필요 없이 연결 여부만 알면 되면 여기서 체크하고 3단계로 이동
갈 수 있는 정점에 대하여 다시 탐색 (반복)

2. DFS - 깊이 우선 탐색(Depth First Search)

재귀 함수 사용

핵심 코드

		//start 를 갈 수 있다는 걸 알고 방문한 상태
    void dfs(int start) {
        //1. visit check
        visit[start] = true;

        //2. 정답 갱신
        sb.append(start).append(' ');

        //3. 갈 수 있는 모든 정점
        for (int i : adjacencyList[start]) {

            //처리하지 않을 정점을 조건문으로 걸러냄
            if (visit[i]) {
                continue;
            }

            //조건을 모두 통과한 정점에 대해 dfs
            dfs(i);    // 재귀 -> 더 깊게 들어감
        }
    }

visit 체크
start가 갈 수 있는 모든 정점에 대해 dfs(재귀)
- 이 때 처리하지 않을 정점을 조건문으로 잘 걸러야 함

3. BFS - 너비 우선 탐색(Breadth First Search)

Queue 사용

핵심 코드

     // start 에서 시작해서 갈 수 있는 정점들을 모두 탐색하기    
    void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();

        //1. 큐에 시작점 넣고 visit check
        queue.add(start);
1번      visit[start] = true;  // start 를 갈 수 있다고 표시하기 (중요!!!)

        //2. 큐에 더 이상 값이 없을 때까지, 즉 갈 수 있는 정점이 없을 때까지 탐색
        while (!queue.isEmpty()) {
            int number = queue.poll();

            //큐에서 꺼낼 때 정답 갱신
            sb.append(number).append(' ');

						// visit[number] = true;
            // visit 체크를 1,2번에서 하지 않고 여기서 하면 특수한 경우에 문제가 발생할 수 있음
						// 반드시 큐에 넣을 때 visit 체크를 해야 함

            //큐에 넣을 수 있는 모든 정점
            for (int i : adjacencyList[number]) {

                //처리하지 않을 정점을 조건문으로 걸러냄
                if (visit[i]) {
                    continue;  // number 에서 i 를 갈 수는 있지만, 이미 탐색한 점이면 무시
                }
                
                //조건을 통과한 정점을 큐에 넣고 visit check
                // y를 갈 수 있으니까 queue 에 추가하고, visit 처리 하기!
                queue.add(i);
 2번             visit[i] = true;
            }
        }
    }

시작점(start)를 큐에 넣고 visit check
while(!queue.isEmpty)
- 큐가 빌 때까지, 즉 갈 수 있는 정점이 더 없을 때 까지 탐색 진행
1. while문 안에서 큐에 있는 정점 하나 꺼냄
2. 해당 정점이 갈 수 있는 모든 정점 체크해서 큐에 넣고 visit check
  - 이 때 처리하지 않을 정점을 조건문으로 잘 걸러야 함