[백준] 14442 벽 부수고 이동하기2

문제소개

• 벽 부수고 이동하기는 BFS 최단 거리 문제입니다.
• 상하좌우를 이동하면서 벽이 없으면 이동할 수 있으며 벽이 있을 때 망치( K > 0 )이면 벽을 부수고 이동할 수 있습니다.
• 벽을 부술 수 있는 망치가 있기 때문에 망치 사용 여부만 잘 확인해주시면 크게 어려운 문제는 아닙니다.

 

문제풀이

• BFS 최단거리를 풀 때 활용되는 Priority Queue를 통해서 cost가 최소가 되는 Item을 우선적으로 처리합니다.
• BFS와 Priority Queue를 통해서 풀기 때문에 특정 x , y에 도달하게 되면 cost가 최소입니다.
• 한 가지 주의해야할 것은 망치의 사용 여부입니다.
• 'START'에서 '여기까지'로 갈 때 비용은 1번, 2번 경로 모두 3(START 포함)입니다.
• 하지만 바로 망치 사용 여부 때문에 해당 위치에서 다른 상태를 갖게 됩니다.
• 이 상태를 표시하기 위해서 visit[x][y][망치수]로 표현하는게 중요합니다.
• visit[x][y][망치수]가 false일 때 Priority Queue에 넣어줘야하기 떄문입니다.
  • (Queue에 넣어 줄수 있을 때 true로 변경합니다.)

• 위 주의사항을 잘 고려하여 board[x][y]에서 벽이 있으면서 망치가 있으면 망치 갯수를 줄이고 cost + 1한 다음queue에 넣고
• board[x][y]에서 벽이 없으면 cost + 1을 한 다음 queue에 넣으면서 Goal에 도달하면 됩니다.

소스코드 보기