kingsubin

그리디&구현, DFS&BFS 본문

Algorithm

그리디&구현, DFS&BFS

kingsubin 2020. 9. 1. 21:52

그리디 & 구현

 

- 시각

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        /**
         * 구현
         * 시각
         * N시 59분 59초까지 3이 하나라도 포함되는 모든 경우의 수
         */
        int h = Integer.parseInt(br.readLine());
        int cnt = 0;

        for (int i = 0; i <= h; i++) {
            for (int j = 0; j < 60; j++) {
                for (int k = 0; k < 60; k++) {
                    if (check(i, j , k)) {
                        cnt ++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }

    public static boolean check(int h, int m, int s) {
        return h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3;
    }
}

​

 

- 곱하기 혹은 더하기 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 곱하기 혹은 더하기
        // S의 길이는 1 ~20 // 0~9의 수로 이루어져있음
        // 가장 큰 수 구하기
        
        String S = br.readLine();
        long ans = S.charAt(0) - '0';

        for (int i = 1; i < S.length(); i++) {
            if (S.charAt(i) - '0' <= 1) {
                ans += (S.charAt(i) - '0');
            } else {
                ans *= (S.charAt(i) - '0');
            }
        }

        System.out.println(ans);
    }
}
​

 

- 좌표 이동하기

import java.util.*;

public class Main {

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

        // N을 입력받기
        int n = sc.nextInt();
        sc.nextLine(); // 버퍼 비우기
        String[] plans = sc.nextLine().split(" ");
        int x = 1, y = 1;

        // L, R, U, D에 따른 이동 방향 
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        char[] moveTypes = {'L', 'R', 'U', 'D'};

        // 이동 계획을 하나씩 확인
        for (int i = 0; i < plans.length; i++) {
            char plan = plans[i].charAt(0);
            // 이동 후 좌표 구하기 
            int nx = -1, ny = -1;
            for (int j = 0; j < 4; j++) {
                if (plan == moveTypes[j]) {
                    nx = x + dx[j];
                    ny = y + dy[j];
                }
            }
            // 공간을 벗어나는 경우 무시 
            if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
            // 이동 수행 
            x = nx;
            y = ny;
        }

        System.out.println(x + " " + y);
    }

}

 


DFS & BFS

 

그래프 탐색이란 ?

- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

 

- DFS

 

1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함

 

2. 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함 

 

3. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

 

4. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

 

5. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

깊이 우선 탐색(DFS)의 특징

- 자기 자신을 호출하는 순환 알고리즘의 형태를 지님

- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

 

깊이 우선 탐색(DFS)의 구현 방법

1. 순환 호출 이용

2. 명시적인 스택 사용

 

 

 

import java.util.ArrayList;

   /**
     * DFS 깊이 우선 탐색
     * 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
     * 스택 자료구조 (혹은 재귀 함수)를 이용,
     * 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
     * 2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면
     * 그 노드를 스택에 넣고 방문처리 한다.
     * 3. 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복         *
     */


public class DFS {

    public static boolean[] visited = new boolean[9]; // 방문처리했는지 확인하기 위한 배열
    public static ArrayList<ArrayList<Integer>> graph
            = new ArrayList<ArrayList<Integer>>(); // 그래프 전체

    // dfs 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");

        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y])  {
                dfs(y);
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

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

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

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

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

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

        // 노드 6에 연결된 노드 정보 저장
        graph.get(6).add(7);

        // 노드 7에 연결된 노드 정보 저장
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);

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

        dfs(1);
    }

}

 

 

- BFS

 

1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

2. 즉 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

 

3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함

 

너비 우선 탐색(BFS)의 특징

- BFS 는 재귀적으로 동작하지 않는다.

- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

- BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함 

- 즉 선입선출(FIFO) 원칙으로 탐색

 

너비 우선 탐색(BFS)의 구현방법

- 자료구조 큐 (Queue)를 이용 

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

/**
 * BFS 너비 우선 탐색
 * 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
 * 큐 자료구조 이용,
 * 1. 탐색 시작 노드를 큐에 삽입하고 방문처리
 * 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서
 * 방문하지 않은노드를 모두 큐에 삽입하고 방문 처리한다.
 * 3. 더 이상 2번의 과정을 수행할 수 없을때까지 반복
 */

public class BFS {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // BFS 함수 정의
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        // 현재 노드를 방문 처리
        visited[start] = true;

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {

            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x + " ");

            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for (int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if (!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

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

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

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

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

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

        // 노드 6에 연결된 노드 정보 저장
        graph.get(6).add(7);

        // 노드 7에 연결된 노드 정보 저장
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);

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

        bfs(1);
    }

}

 

 

- 음료수 채우기

 

import java.io.*;
import java.util.StringTokenizer;

/**
 * 음료수 얼려 먹기
 * 첫 번째 줄에 얼음 틀의 세로길이 N, 가로길이 M / N,M : 1~1000
 * 두 번째 줄부터 N+1 번째 줄까지 얼음틀의 형태
 * 0 : 구멍이 뚫린 부분, 1 : 막힌 부분
 * 한 번에 만들 수 있는 아이스크림의 개수 ?
 */

/**
 * DFS 활용
 * 1. 특정한 지점의 주변의 상, 하, 좌, 우를 살펴본 뒤에
 * 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
 * 2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면,
 * 연결된 모든 지점을 방문할 수 있다.
 * 3. 모든 노드에 대하여 1~2 번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트한다.
 */

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) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n, m 입력
        n = Integer.parseInt(st.nextToken()); // 세로 길이
        m = Integer.parseInt(st.nextToken()); // 가로 길이

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 모든 노드(위치)에 대하여 음료수 채우기
        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);
    }
}


 

- 미로 탈출 

 

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

/**
 * 미로 탈출
 * 첫째 줄에 두 정수 N, M  4~200
 * 다음 N개의 줄에는 각각 M개의 정수 (0, 1)의 미로 정보가 주어진다.
 * 또한 시작과 마지막 칸은 항상 1이다.
 * 괴물이 있는 부분 0, 괴물이 없는 부분 1
 * 한 번에 한 칸씩 이동, 시작칸, 마지막칸 포함
 * 탈출하기 위해 움직여야 하는 최소 칸의 개수 ?
 */

class Node {
    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public int getIndex() {
        return index;
    }

    public int getDistance() {
        return distance;
    }
}

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<Node> q = new LinkedList<>();
        q.offer(new Node(x, y)); // 큐에 노드 넣기

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            Node node = q.poll(); // 꺼내기
            x = node.getIndex();
            y = node.getDistance();

            // 현재 위치에서 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(); // 버퍼지우기

        // 맵 정보 입력 받기
        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';
            }
        }

        // 결과 출력
        System.out.println(bfs(0, 0));
    }
}

 

 


※참조

github.com/ndb796/python-for-coding-test

 

 

'Algorithm' 카테고리의 다른 글

다이나믹 프로그래밍 정리  (0) 2020.09.09
트리 정리  (0) 2020.09.07
그리디&구현, DFS&BFS  (0) 2020.09.01
LinkedList  (0) 2020.08.31
EOF (End of File)  (0) 2020.08.29
정렬 정리  (0) 2020.08.27
0 Comments
댓글쓰기 폼
Prev 1 2 3 4 5 6 7 8 9 10 Next