백준 1937. 욕심쟁이 판다

티스토리 뷰

tose33 2022. 8. 2. 12:34

1937번: 욕심쟁이 판다

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에

www.acmicpc.net

처음에 dp와 bfs 로 해결하려 했다가 시간초과나서 결국 dfs로 다시 풀었다.

문제의 핵심은 판다가 한번 방문한 곳은 다시 방문할 필요가 없다는 것이다.

다음 지점을 계산했는데 다음 지점이 이미 방문한 곳이라면 어처피 해당 지점에서 부터 이어지는 길들은 모두 이미 방문한것이기 때문이다.

d[r][c] : (r,c) 지점에서 시작해 최대로 이동할수 있는 횟수

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함