[백준] 1937 욕심쟁이 판다

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

입력으로 주어지는 대나무 숲의 크기가 크므로 모든 좌표에 대해 이동 가능한 거리를 탐색하면 시간 초과 문제가 발생합니다.

그러므로 각 좌표에 이동 가능한 최대의 거리를 기록이 필요하여 DP를 이용하였습니다.

 

처음에 BFS를 이용하여 가장 적은 대나무 양의 좌표를 탐색하여 이동 가능한 거리를 기록하였고, 기록이 안된 좌표들이 남아있을 경우 다음으로 적은 대나무 양을 가진 좌표를 탐색하여 거리를 구하였습니다.

그러나 기록이 되지 않은 좌표들이 남아있을 때 마다 계속해서 2차원 배열 탐색이 필요하였고, 이전에 기록한 이동 가능한 거리가 탐색의 경우에 따라 값이 변하게 되었습니다. 이러한 과정으로 인해 탐색의 양이 증가하여 시간 초과가 발생하였습니다.

 

이러한 문제를 해결하기 위해 2차원 배열을 한번만 탐색하여 좌표에 기록한 거리가 있으면 탐색하지 않고, 기록이 되어 있지 않으면 해당 좌표에서 이동 가능한 거리를 구하여 정답을 기록하도록 변경하였습니다.

2) 알고리즘

• DP
• 재귀
• DFS

3) 풀이 코드

사용 언어 - Python

import sys
sys.setrecursionlimit(1000000)
sys.stdin = open('input.txt')

dr = [-1, 0, 1, 0]                  # 상 우 하 좌
dc = [0, 1, 0, -1]

def solution(y, x):
    if visited[y][x]:               # 해당 좌표에서 최대로 이동 가능한 경로를 이미 아는 경우
        return visited[y][x]        # 남은 이동 수 반환
    
    visited[y][x] = 1               # 현재 좌표에서 1칸 이동 가능하다고 설정
    for k in range(4):              # 인접 좌표 확인
        r = y + dr[k]
        c = x + dc[k]

        if 0 <= r < N and 0 <= c < N and board[y][x] < board[r][c]:     # 현재 좌표보다 더 많은 대나무가 있으면
            visited[y][x] = max(visited[y][x], solution(r, c) + 1)      # 재귀로 다음 좌표 탐색
    return visited[y][x]                                                

N = int(sys.stdin.readline())                                               # 대나무 숲 크기
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]    # 대나무 숲 정보
visited = [[0] * N for _ in range(N)]                                       # 좌표별 이동 가능한 수
answer = 0

for i in range(N):
    for j in range(N):
        if not visited[i][j]:                       # 현재 좌표에서 이동 가능한 경로 수를 모르는 경우
            answer = max(answer, solution(i, j))    # 탐색하고, 정답과 비교하여 더 큰 값 저장
print(answer)

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다