Develop Destroyer

https://www.acmicpc.net/problem/1520

2차원 Array가 주어졌을때 0,0에서 시작하여 상하좌우로 이동할 때, 항상 높은 값에서 낮은 값의 방향으로 이동 할 수 있는 모든 케이스에 대해 출력하라는 문제이다.

시간복잡도를 고려해야하는 문제로 dp를 이용해야한다.

dp를 이용하는 것은, 여러개의 경로를 계산하는 과정에서 중복된 경로를 고려해야 하기 때문이다.

/** 3번 내리막 길 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static int N, M;

    static int graph[][];
    static int dp[][];

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        graph = new int[N][M];
        dp = new int[N][M];

        for(int i=0; i<N;i++) {
            for(int j=0; j<M; j++){
                graph[i][j] = sc.nextInt();
//                dp[i][j] = Integer.MIN_VALUE;
            }
        }
        sc.close();
/*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String nm = br.readLine();
        N = Integer.parseInt(nm.split(" ")[0]);
        M = Integer.parseInt(nm.split(" ")[1]);

        graph = new int[N][M];
        dp = new int[N][M];

        for (int i = 0; i < N; i++) {
            nm = br.readLine();
            for (int j = 0; j < M; j++) {
                graph[i][j] = Integer.parseInt(nm.split(" ")[j]);
                // dp[i][j] = -1;
            }
        }

 */
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i],Integer.MIN_VALUE);
        }
        System.out.println(dfs(0, 0));

    }

    public static int dfs(int x, int y) {
        if(x == N-1 && y == M-1) {
            return 1;
        }
        if  (dp[x][y] != Integer.MIN_VALUE) {
            return dp[x][y];
        }
        else {
            dp[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < N && nx >= 0 && ny < M && ny >= 0) {
                    if (graph[x][y] > graph[nx][ny]) {
                        dp[x][y] += dfs(nx, ny);
                    }
                }
            }
        }
        return dp[x][y];


    }
}

큐를 이용해서 구현하며, 기본적인 BFS 탐색 순서는 다음과 같다.

1. 큐를 하나 만든다

2. 시작할 노드를 넣는다

3. 시작할 노드를 꺼내고 출력한다

4. 인접한 노드를 큐에 넣는다

5. 이 때, 한번 큐에 넣었던 노드는 다시 큐에 넣지 않아야 한다

BFS 관련된 문제로 소스코드로 확인해보자

백준 토마토 문제이다.

https://www.acmicpc.net/problem/7569

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static int N, M, H;
    public static int[][][] box;

    public static int[] dx = {1, -1, 0, 0, 0, 0};
    public static int[] dy = {0, 0, 1, -1, 0, 0};
    public static int[] dz = {0, 0, 0, 0, 1, -1};

    public static Queue<Tomato> queue = new LinkedList<Tomato>();

    static class Tomato {
        int x, y, z;

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

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken()); /** 1번 문제는 변수 H를 1로 주면 해결된다.. */

        box = new int[H][N][M];

        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < M; j++) {
                    box[k][i][j] = Integer.parseInt(st.nextToken());
                    if(box[k][i][j] == 1){
                        queue.offer(new Tomato(i, j, k));
                    }
                }
            }
        }

        bfs();
    }

    static int isPerfectlyRipe () {
        int max = -10000000;
        for (int k = 0; k < H; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (box[k][i][j] == 0) {
                        return 0;
                    }
                    max = max > box[k][i][j] ? max : box[k][i][j];
                }
            }
        }
        return max;
    }

    public static void bfs() {

        while (!queue.isEmpty()) {
            Tomato tomato = queue.poll(); // 큐에서 익은 토마토를 하나 꺼내자

            for (int i = 0; i < 6; i++) { // 상하좌우위아래 6개 방향으로 이동했을 때의 각 토마토 확인
                int _x = tomato.x + dx[i];
                int _y = tomato.y + dy[i];
                int _z = tomato.z + dz[i];
                if(0 <= _x && _x < N &&
                        0 <= _y && _y < M &&
                        0 <= _z && _z < H) { // 이동한 장소가 배열의 크기를 벗어나지 않도록 해야한다
                    if (box[_z][_x][_y] == 0) { // 아직 안익었다면 큐에 넣어준다
                        box[_z][_x][_y] = 1; //이제 익었으니까 1로 변환해주어야 다음 탐색을 이어나갈 수 있다
                        queue.add(new Tomato(_x, _y, _z));
                        box[_z][_x][_y] = box[tomato.z][tomato.x][tomato.y] + 1; // 날짜정보를 저장해준다 이 정보는 1부터 시작했으니 결과에서 1을 빼주어야한다
                    }
                }
            }
        }

        System.out.println(isPerfectlyRipe() - 1);

    }
}

참고URL : http://hsp1116.tistory.com/33

대학시절 알고리즘 시간에 배우는 아주 기본적인 정렬방법들인데,,

위 URL 블로거분이 알고리즘 코드와 설명이 자세히 포스팅해두셨다.

버블정렬은 은유적인 네이밍덕에 어떤 알고리즘인지 금방 연상이 되는데

선택, 삽입정렬은 헷갈린다..

이번 기회에 제대로 머리에 기억해야지..

결론적으로 이 세가지 알고리즘은 일반적으로 시간복잡도 O(n^2)을 따르지만,(인덱스를 하나하나 접근하여 비교하므로)

삽입정렬 최선의 경우 미리 정렬된 상태일 때 O(n)에 해당되는 복잡도를 가지고 있다는 것이고,

버블정렬의 경우 별도의 스위치 장치를 해두면 미리 정렬되어 있을 경우 O(n)만큼의 시간복잡도를 가지게 할 수 있다.