문제 링크입니다: https://www.acmicpc.net/problem/2842
2842번: 집배원 한상덕
문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막
www.acmicpc.net
특이한 유형의 BFS 문제였습니다.
상하좌우 뿐만 아니라 대각선도 탐색해야하고 피로도도 고려해야합니다.
이 문제에서의 핵심은 입력받은 피로도를 정렬한 뒤 중복된 숫자를 삭제하는 것이었습니다.
이후에는 low, high를 설정하여 현재 칸이 tiredness[low]와 tiredness[high] 내에 있을 경우에만 밟도록 시뮬레이션을 돌리는 것입니다.
시뮬레이션을 돌리며 모든 집을 방문했을 경우에만 결과를 갱신하면 됩니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1766번 문제집 (0) | 2019.09.29 |
|---|---|
| 백준 16674번 2018년을 되돌아보며 (0) | 2019.09.25 |
| 백준 3649번 로봇 프로젝트 (0) | 2019.09.21 |
| 백준 1662번 압축 (0) | 2019.09.18 |
| 백준 15655번 N과 M (6) (2) | 2019.08.28 |