https://www.acmicpc.net/problem/1937
💡문제이해 : 욕심쟁이 판다는 상,하,좌,우로 이동할 수 있는데 단 머물러 있던 자리보다 대나무가 많아야 한다.
즉, 더 큰 수로만 이동할 수 있다. 최대한 많은 칸을 이동할 때 칸의 수를 구해라.
🤔 만일 2에서 이동한다고 하면 2→ 5 →11 →15 , 2→ 15, 2→ 13, 2→ 16으로 이동 가능
1. 대나무 숲 정보 입력받아오기
n = int(input())
arr = [list(map(int,input())) for _ in range(n)]
2. 재귀함수로 갈 수 있는 경우의 수 구하기
- 아무것도 방문하지 않았을 때 point = 0으로 설정
- 상,하,좌,우 4가지 방향으로 탐색
- 만일 이동하고자 하는 좌표가 그래프 안에 있고, 더 크다면 방문하여 point 업데이트
def recur(y,x) :
point = 0
# 4가지 방향으로 탐색
for dy,dx in [[-1,0],[1,0],[0,1],[0,-1]] :
ey,ex = y+dy , x+dx
#이동하는 좌표가 그래프 안에 있고
if 0<= ey < n and 0<= ex < n :
#해당 좌표보다 큰 곳으로 이동
if arr[y][x] < arr[ey][ex] :
#너가 이동하여 한번이라도 방문했다면 point update
point = max(point,recur(ey,ex) + 1))
return point
3. 모든 좌표에서 탐색 (좌표와 경우의 수 출력)
for y in range(n) :
for x in range(n) :
answer = recur(y,x)
print(y,x,answer)
⇒ 실행결과
(0,0) 좌표에서 갈 수 있는 최대 이동 횟수 : 0
(0,1) 좌표에서 갈 수 있는 최대 이동 횟수 : 2
(0,3) 좌표에서 갈 수 있는 최대 이동 횟수 : 1
⁝
4. DP로 변경
def recur(y,x) :
if dp[y][x] != 0 :
dp[y][x]
for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]] :
ey,ex = y+dy , x+dx
if 0 <= ey < n and 0 <= ex < n :
if graph[y][x] < graph[ey][ex] :
dp[y][x] = max(dp[y][x] , recur(ey,ex) +1)
return dp[y][x]
n =int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for i in range(n) for _ in range(n)]
for y in range(n) :
for x in range(n) :
recur(y,x)
print(dp)
#최대 칸의 개수 출력
print(max(map(max,dp)) + 1 )
#실행결과 4
위와 같이 풀었을 때 시간초과가 나버렸다.. 🤔
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[프로그래머스] Lv1 문제풀이 (1) | 2023.10.09 |
---|---|
[프로그래머스] Lv1 문제풀이 (0) | 2023.10.09 |
[백준] 10815번 숫자카드 - 파이썬 (0) | 2023.10.06 |
[백준] 2805번 나무자르기 - 파이썬 (1) | 2023.10.06 |
[백준] 2606번 바이러스 - 파이썬 (2) | 2023.10.05 |