728x90

섹션 2. 코딩테스트 - 05. 탐색

⬛ 05. 탐색 (= 순회)

그래프의 순회
한 정점에서 시작하여 그래프의 모든 정점을 ‘한 번씩’ 중복 없이 방문하는 것

🏓그래프 순회의 종류

1) DFS (깊이 우선 탐색)

한 정점에서 시작하여 깊이 탐색하다가 다시 직전 정점으로 돌아와 깊이 탐색을 반복

(1) 정점 v 방문

(2) 정점 v에 대한 인접 정점들 中 (1개) 방문

방문 안한 w 존재 O : v 방문처리(push) 후, w 방문 (DFS(v) )
방문 안한 w 존재 X : 더이상 방문할 w들이 존재하지 않으므로 복귀 pop

(3) 스택(DFS) 공백되면 종료

2) BFS (너비 우선 탐색)

시작 정점에 대한 인접 정점들 모두를 차례로 방문하고, 다시 처음 방문했던 정점으로 되돌아와 너비 우선 탐색 반복

(1) 정점 v 방문

(2) 정점 v에 대한 인접 정점들 (모두)

방문 안한 정점들 차례로 방문하여 큐에 enqueue
더 이상 방문 안한 인접 정점들 없으면 큐 dequeue 하여 정점v 재설정 후 (2)를 반복

(3) 큐 공백되면 종료

⬛ 05-1. 깊이 우선 탐색 DFS

🟦 깊이 우선 탐색

시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 리턴하여 다음 분기로 이동한 뒤 깊이 탐색을 다시 반복하는 알고리즘
시간 복잡도 O(V + E)
재귀함수 활용하므로 스택 오버플로우 주의

🟧 깊이 우선 탐색 핵심

노드 방문 여부 배열 visited[] 따로 선언 필요
한 번 방문한 노드는 다시 방문 하면 안되기 때문에 방문 체크용임

🟦 백준 11724번. 연결 요소의 개수 구하기

만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행 되었을 것이다.
다시 말해 모든 노드 탐색하는 데 실행한 DFS 횟수가 곧 연결 요소의 개수인 것.

/*백준 11724번. 연결 요소의 개수 
 *  연결 요소의 개수 = 만약 모든 노드가 연결되어있다면 깊이있게 쭉 순회하여 DFS 최초 호출1 로 모두 리턴 받으니 cnt = 1일 것이다.
 *  즉, 모든 노드 탐색을 위해 실행한 DFS의 횟수가 == 연결 요소의 개수가 되는 것.
 * */
package to_0608_3;
/*다시 풀어보기 */

import java.util.*;

public class Main {

    static ArrayList<Integer>[] A;
    static boolean visited[];
    //DFS
    static void DFS(int v) {
        if(visited[v]) {
            return;
        }
        visited[v] = true;
        for(int x : A[v]) {
            if(visited[x]==false) {
                DFS(x);
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner kb= new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();

        visited = new boolean[n+1];

        A = new ArrayList[n+1];
        for(int i=1; i<n+1; i++) {
            A[i] = new ArrayList<>();//각 공간 생성 
        }

        //입력받기 정보
        for(int i=0; i<m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            //양방향 쌍으로 넣기
            A[a].add(b);
            A[b].add(a);
        }

        //전체 노드 순회하면서 DFS호출 
        int cnt = 0;
        for(int i=1; i<n+1; i++) {
            if(!visited[i]) {
                cnt++;
                DFS(i);
            }
        }

        System.out.println(cnt);
    }

}

🟦 백준 2023번. 신기한 소수 DFS 풀이

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

이 문제는 N자릿수의 수 각각의 자릿수가 확장될 때마다 모든 수가 소수여야 신기한 소수가 되는 문제이다.
DFS(int v, int lv) 로 각 자릿수 lv별로 확장을 해가되, lv == N 자릿수가 되면 해당 수가 소수인지 판별 후 출력하도록 한다.
최초 시작 값은 2, 3, 5, 7 인데, 이유는 1의 자리수에서 홀수인 수가 2 ,3 ,5, 7뿐이므로 이 숫자부터 시작해서 각각 DFS 깊이 있게 순회하며 소수인 수로 확장해나가야 하기 때문,
무엇보다도, 들어온 수가 짝수일 경우 2를 항상 약수로 갖게 되므로 소수가 안된다. 따라서 짝수인 경우도 제외시켜야 한다.

package to_0608_4;

import java.util.*;

/* 2023번. 신기한 소수 
 * */
public class Main {
    static int N;//소수 
    //DFS
    static void DFS(int v, int lv) {//각 레벨별 자릿수 
        if(lv == N) { //탐색 레벨 종료되면 
            if(isPrime(v)) {
                System.out.println(v);
            }
            return;//없으면 그냥 복귀 
        }

        for(int i=1; i<10; i++) {//1~9까지의 값들 중 
            if(i % 2 == 0) {
                continue;// 짟수 제외 
            }
            if(isPrime(v * 10 + i)) {//현재 자릿수 밀고 + 홀수로만 연결해서 
                DFS(v*10+i, lv+1);//다음 자릿수에 대한 레벨로 호출
            }
        }
    }
    //소수 판별
    static boolean isPrime(int num) {
        for(int i=2; i<=num/2; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }

    //메인
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb= new Scanner(System.in);
        N = kb.nextInt();//자릿수 

        //각 자릿수가 모두 소수여야 하는데.

        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);

    }

}

🟦 백준 13023번. 친구 관계 파악하기

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

=> 나의 풀이

이 문제는 DFS인데, A-B-C-D-E가 모두 친구이려면 깊이 5가 되어야 한다는 거다.
깊이 5까지 내려가서 값이 존재할 경우 arrive 값을 true를 주고 break 하나라도 존재하면 되니까. 이때 arrive 값을 기준으로 true이면 1을, false이면 0을 출력하도록 한다.
가장 중요한 건. 아직 깊이가 5까지 or arrive 처리 전인 상태의 시작 정점에 대해서는 visited[]값도 false 로 세팅해준 뒤 DFS가 복귀해야 한다.

package to_0608_5;

import java.util.ArrayList;
import java.util.Scanner;

/* 13023번. 친구 관계 파악하기 
 * */
public class Main {
    static ArrayList<Integer> [] A;
    static boolean visited[];
    static boolean arrive;

    //DFS()
    static void DFS(int v, int lv) {
        if(lv == 5 || arrive ) {
            arrive = true;
            return;
        }

        visited[v] = true;
        for(int i : A[v]) {
            if(!visited[i]) {
                DFS(i, lv+1);
            }
        }
        //여기서 false 주는 이유 
        //다시 복귀할 때, 다른 뿌리로 lv 깊이 탐색 해야 하기 때문에 다 탐색한 뒤엔 false 준 뒤 복귀할 것.
        visited[v] = false;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();

        visited = new boolean[n];
        A = new ArrayList[n];

        for(int i=1; i<n; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for(int i=0; i<m ; i++) {
            int a= kb.nextInt();
            int b = kb.nextInt();
            A[a].add(b);
            A[b].add(a);
        }
        //brak 걸어줄 용도 임
        arrive = false;

        for(int i=0; i<n; i++) {
            DFS(i, 1);

            if(arrive) break;
        }

        if(arrive == true) {
            System.out.println("1");
        }else {
            System.out.println("0");
        }

    }

}

⬛ 05-2. 너비 우선 탐색 BFS

🟦 너비 우선 탐색 BFS

시작 노드에서 출발하여 인접 정점들을 모두 방문하며 탐색하는 알고리즘
선입선출 방식 탐색이므로 ‘큐’를 사용
목표 노드에 도착하는 경로가 여러 개일 때 최단 겨올를 보장한다.
= 기본적으로 탐색 시작 노드에서 가까운 노드를 우선 탐색하는 기법이기 때문

🟧 너비 우선 탐색 핵심

DFS와 마찬가지로 BFS도 한 번씩 중복없이 전체 노드 순회하는 게 목적이다.
따라서, 방문 체크 배열 [] 을 따로 선언하는 것 필요

🏓 BFS 순서

(1) 일단 정점 v 큐에 enqueue 삽입

(2) 정점 v 방문 체크 후 → v 를 dequeue 빼고, v에 대한 인접 정점들을 모두 큐에 enqueue

(3) 더이상 방문 안한 인접 정점이 없다 → 큐 dequeue해서 새 정점 v 지정. ⇒ (2) 를 반복

(4) 큐 공백 되면 종료

🟦 백준 1260번. DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*1260번. DFS. BFS 프로그램 */
public class Main {
    //정적 변수 
    static ArrayList<ArrayList<Integer>> graph;    
    static boolean visited[];
    static int n, m;

    //DFS 
    static void DFS(int v) {
        //이미 방문한 정점이면 그냥 리턴 복귀
        if(visited[v]) return;

        //아니면 v 방문 처리 
        visited[v] = true;
        System.out.print(v+" ");
        //v에 대한 인접정점 꺼내서 DFS 깊이 탐색 
        for(int x : graph.get(v)) {
            if(!visited[x]) {
                DFS(x);
            }
        }
    }
    //BFS 
    static void BFS(int v ) {
        Queue<Integer> Q = new LinkedList<>();

        Q.offer(v);//현재 정점 v를 큐에 담기 
        visited[v] = true; //방문 처리 

        //모두 탐색해야 하므로 whiel
        while(!Q.isEmpty()) {
            int cur = Q.poll();//현재 정점 뽑고
            System.out.print(cur+ " ");
            for(int nv : graph.get(cur)) {
                if(!visited[nv]) {
                    Q.offer(nv);
                    visited[nv] = true;
                }
            }
        }
    }


    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner kb = new Scanner(System.in);
        n= kb.nextInt();
        m =kb.nextInt();

        int s = kb.nextInt();//시작 정점 

        //공간 생성 
        graph = new ArrayList<ArrayList<Integer>>();
        //방문 체크
        visited = new boolean[n+1];

        for(int i=0; i<=n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        //간선 개수만큼 정보 입력받음 
        for(int i=0; i<m ; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            //양방향 정보 담기 
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        //단, 방문 가능한 정점 여러개 인 경우 정렬 
        for(int i=0; i<=n; i++) {
            Collections.sort(graph.get(i));//각각 연결 정점들 정렬
        }

        //시작 정점에 대한 호출 
        DFS(s);
        System.out.println();//공백 
        visited =new boolean[n+1];//다시 초기화
        BFS(s);

    }

}

🟦 백준 2178번. 미로 탐색 (BFS)

참고 블로그 https://iseunghan.tistory.com/312

풀이 설명

이 문제를 BFS 로 풀어야 하는 이유. 우선 BFS는 현재 정점 인근의 가까운 거리 먼저 탐색할 것임
이 문제는 [][] 2차원 배열로 입력받은 기존의 길 값에 거리를 확장해가며 푸는 문제이다.
BFS는 가까운 거리 먼저 둘러보면서 가기 때문에 여러 경로 중 최단 거리 구할 떄 사용 가능
큐에서 서로의 경로를 하나씩 넣고 빼고 하기 때문에 결국엔 가장 빠른 경로를 먼저 도달하여 배열에 값을 넣게 된다. 그렇게 되면 자연스럽게 오래 걸린 경로는 배열에 값을 넣으려고 해도 이미 값이 있기 때문에 값을 넣지 못하게 되는 것이다!

package to_0609_4;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*미로탐색 다시 풀기 */
//좌표 객체 
class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    //static
    static boolean[][] visited;//방문 체크 배열 
    static int n, m;//가로 세로
    static int[][] A;//원본 배열 
    //상하좌우 좌표 
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

    //BFS
    static void BFS(int x, int y) {
        Queue<Point> Q= new LinkedList<>();
        //방문 처리 
        Q.offer(new Point(x, y));
        visited[x][y] = true;

        while(!Q.isEmpty()) {
            Point cur = Q.poll();//현재 정점뽑고
            for(int i=0; i<4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                //좌표가 경계선 벗어나면 패스 
                if(nx<0 || ny<0 || nx >=n ||ny>=m) continue;
                //좌표의 값이 벽이 0 아니고, 방문 전이어야 함 그 외는 패스
                if(A[nx][ny] == 0 || visited[nx][ny] == true) continue;

                //그 외는 정상 
                Q.offer(new Point(nx, ny));
                visited[nx][ny] = true;
                A[nx][ny] = A[cur.x][cur.y]+1;//직전 거리의 +1값으로 갱신 
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        //입력만 다시 받아야 한다. 왜냐면 붙여서 라인단위로 읽으니까 구분자 필요
        n = kb.nextInt();
        m = kb.nextInt();
        A = new int[n][m];

        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                A[i][j]= kb.nextInt();
            }
        }

        BFS(0,0);//호출하면 A갱신되니까
        System.out.println(A[n-1][m-1]);//n,m 좌표 출력 
    }

}