[백준/BOJ] 1520 내리막 길 - JAVA - 골드3

2024. 5. 29. 18:24·알고리즘/문제풀이

[백준/BOJ] 1520 내리막 길 - JAVA - 골드3

문제

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

문제 분석

조건

  • 왼쪽 위에서 시작하여 오른쪽 아래로 이동하는 것이 목표
  • 현재 숫자보다 작은 인접한 숫자로만 이동할 수 있음
  • 가능한 경로의 수를 출력

풀이방법

    • DFS를 이용하여 경로를 탐색하며 DP를 이용하여 방문했던 점엔 다시 방문하지 않는 방법을 이용했습니다.

DP 테이블을 -1로 초기화 한 뒤 출발지점부터 탐색을 시작
현재 좌표에 이미 방문을 했으면 현재 좌표의 DP값을 반환하고, 첫 방문(-1)일 시 0으로 DP값을 업데이트

DFS 탐색을 시계방향으로 했을 때 아래와 같은 상황이 된다.

방법을 반복하여 목표 지점에 도달하였을 경우 1를 반환하고 이를 이전 좌표 DP값에 업데이트 한다.

DP값을 업데이트 하여 돌아갈때 `[0, 3]`좌표에서는 아래 방향으로 한번 더 탐색을 할 수 있게 된다. 이때는 방문하지 않고 방문해야할 지점인 DP[1, 3]의 값을 현재 DP값으로 더하면 된다.
같은 방법으로 계속 진행하여 아래를 탐색하면

위와 같은 모양이 되고, 같은 방법으로 방문해야할 지점의 DP값이 -1이 아니면 해당 값을 현재 DP값으로 더하면 된다.

최종적으로 DP 표는 위와 같은 모양이 되며, `[0, 0]`의 값인 3이 답이 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int R;
    static int C;
    static int[][] map;
    static int[][] dp;
    static int[][] dr = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

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

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];
        dp = new int[R][C];
        for (int r = 0; r < R; r++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(dp[r], -1);
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(dfs(0, 0));
    }

    private static int dfs(int r, int c) {
        if (r == R - 1 && c == C - 1) {
            return 1;
        }
        if (dp[r][c] != -1) {
            return dp[r][c];
        }
        dp[r][c] = 0;
        for (int[] d : dr) {
            int nextR = r + d[0];
            int nextC = c + d[1];
            if (nextR < 0 || nextC < 0 || nextR >= R || nextC >= C) {
                continue;
            }
            if (map[r][c] > map[nextR][nextC]) {
                if (dp[nextR][nextC] != -1) {
                    dp[r][c] += dp[nextR][nextC];
                    continue;
                }
                dp[r][c] += dfs(nextR, nextC);
            }
        }
        return dp[r][c];
    }
}

결과

728x90
저작자표시 비영리 변경금지 (새창열림)
'알고리즘/문제풀이' 카테고리의 다른 글
  • [백준/BOJ] 11053 가장 긴 증가하는 부분 수열 - JAVA
  • [백준/BOJ] 14939 불 끄기 - JAVA
  • [백준/BOJ] 1700 멀티탭 스케줄링 - JAVA
  • [백준/BOJ] 1014 컨닝 - JAVA
LIRI
LIRI
  • LIRI
    기록
    LIRI
  • 전체
    오늘
    어제
    • 분류 전체보기 (73)
      • 블로그 꾸미기 (0)
      • Spring (6)
      • React (3)
      • CS (0)
      • 알고리즘 (57)
        • 개념 (2)
        • 문제풀이 (54)
      • Java (1)
      • DB (1)
      • log (4)
        • SSAFY (3)
        • 궁금 (1)
  • 블로그 메뉴

    • 홈
    • 방명록
  • 공지사항

  • 인기 글

  • 태그

    Spring
    불 끄기
    SSAFY
    Java
    비트마스킹
    SSAFY 9기
    ssafy 합격 후기
    BFS
    dp
    알고리즘 문제풀이
    BOJ
    알고리즘
    lv3
    JWT
    Security
    springboot
    LV2
    dfs
    Springsecurity
    LIS
    pccp모의고사
    백준
    프로그래머스
    그리디
    최장증가부분수열
    도대체왜
    너비우선탐색
    리액트
    싸피
    골드1
  • 최근 댓글

  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
LIRI
[백준/BOJ] 1520 내리막 길 - JAVA - 골드3
상단으로

티스토리툴바