💯Problem Solving
[BOJ] 1520 내리막길
date
Aug 12, 2023
slug
boj-1520
author
status
Public
tags
Python
BOJ
summary
백준 1520번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 12, 2023 01:38 AM
문제 링크
문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
문제풀이
처음에 4방향 BFS로 풀었으나, 12% 에서 시간초과, 이유는 중복된 경로 탐색 때문에
500x500 탐색을 최악의경우 500x500번을 더 하는 것이기 떄문에
의 시간 이 걸리기 때문에 시간초과가 나게된다.
DFS로 탐색하면서 역으로 DP처리해주면 시간초과 나지 않고 풀리게된다.
파이썬 문제풀이 코드
import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] def dfs(y, x): if y == N-1 and x == M-1: return 1 if checked[y][x] != -1: return checked[y][x] checked[y][x] = 0 for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < M and 0 <= ny < N: if arr[y][x] > arr[ny][nx]: checked[y][x] = checked[y][x] + dfs(ny, nx) return checked[y][x] # 삽입 arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) checked = [[-1] * M for _ in range(N)] # checked[0][0] = 1 # [print(arr[i]) for i in range(len(arr))] # print(bfs()) dfs(0, 0) print(checked[0][0]) # print(checked[N-1][M-1]) # [print(checked[i]) for i in range(len(checked))]
시간복잡도
- O(NlogM)
입력
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.
출력
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.