Develope Story

2019-03-26 [JAVA]백준 1520번 - 내리막 길

26 Mar 2019 | java algorithm_study

문제출처

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

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

img

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

img

img

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

문제 접근 방법 1 (실패 - 메모리 초과)

  • bfs를 이용하여 자기 자리 보다 수치가 작은 곳으로 이동하여 총 경로 수 체크
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Baekjoon_1520 {
    static way[][] map;
    static int[] x = {-1, 0, 1, 0};
    static int[] y = {0, 1, 0, -1};
    static int n, m;
    static int count = 0;

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

        n = sc.nextInt();
        m = sc.nextInt();
        map = new way[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = new way(j, i, sc.nextInt());
            }
        }
        //0,0에서 시작
        bfs(map[0][0]);

        System.out.println(count);
    }
    //bfs
    public static void bfs(way w) {
        Queue<way> q = new LinkedList<>();
        q.offer(w);

        while (!q.isEmpty()) {
            way tmp = q.poll();

            for (int i = 0; i < 4; i++) {
                int wx = tmp.x + x[i];
                int wy = tmp.y + y[i];

                if (wx >= 0 && wy >= 0 && wx < m && wy < n) {
                    if (map[wy][wx].value < map[tmp.y][tmp.x].value) {
                        q.offer(map[wy][wx]);
                        //도착했을때
                        if (wy == n - 1 && wx == m - 1)
                            count++;
                    }
                }
            }
        }
    }
}

class way {
    int x, y;
    int value;

    way(int x, int y, int value) {
        this.x = x;
        this.y = y;
        this.value = value;
    }
}

문제접근 방법2 (DFS)

=> m-1, n-1부터 dfs로 추적


import java.util.Scanner;

public class Baekjoon_1520 {
    static int[][] map, dp;
    static int n, m;
    static int[] wx = {-1, 0, 1, 0};
    static int[] wy = {0, -1, 0, 1};

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

        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        dp = new int[n][m];

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

        System.out.println(dfs(m-1, n-1));
    }

    public static int dfs(int x, int y) {
        if (x == 0 && y == 0)
            return 1;

        if (dp[y][x] == 0) {
            for (int i = 0; i < 4; i++) {
                int ny = y + wy[i];
                int nx = x + wx[i];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    if (map[ny][nx] > map[y][x]) {
                        dp[y][x] += dfs(nx, ny);
                    }
                }
            }
        }
        return dp[y][x];
    }
}

=> 시간초과

  • dp값을 -1로 선언해주어 방문시 0으로 바꾸면서 체크 (참고. https://mygumi.tistory.com/231)

import java.util.Scanner;

public class Baekjoon_1520 {
    static int[][] map, dp;
    static int n, m;
    static int[] wx = {-1, 0, 1, 0};
    static int[] wy = {0, -1, 0, 1};

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

        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
                dp[i][j] = -1; //dp를 -1로 초기화
            }
        }

        System.out.println(dfs(m-1, n-1));
    }

    public static int dfs(int x, int y) {
        if (x == 0 && y == 0)
            return 1;

        if (dp[y][x] == -1) {
            dp[y][x] = 0; //방문시 0으로 체크
            for (int i = 0; i < 4; i++) {
                int ny = y + wy[i];
                int nx = x + wx[i];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    if (map[ny][nx] > map[y][x]) {
                        dp[y][x] += dfs(nx, ny);
                    }
                }
            }
        }
        return dp[y][x];
    }
}
  • 내리막기로 갈수 있는 경우의 수 = 도착지점으로 부터 시작지점까지 오르막기 경우의 수
  • dp값을 -1로 초기화 하여 방문시 0으로 변경하는 방식으로 방문 체크

Related Posts

Comments