14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
기본적인 bfs문제다.
내가 이미 방문했던 곳을 표시하는 배열이 필요한데
3차원 배열로 벽을 몇번 뚫었나를 체크한다.
풀이과정
{x,y, 벽뚫은 횟수} 세가지 정보를 담아서 큐에 넣는다.
여기서 큐에 넣는 방법은 두가지로 갈린다.
1. 다음칸이 벽인경우
2. 다음칸이 뚫려있는경우
다음 칸이 벽인경우 현재 내가 (벽을 뚫은 횟수+1) 가 있는 check배열에 이전까지 왔었던 거리에 +1을 해서 더해준다.
다음칸이 뚫려있는 경우는 내가 (벽을 뚫은 횟수) 가 있는 check 배열에 이전까지 왔었던 거리에 +1을 해준다.
그리고 큐에서 정보를 꺼낼 때, 만약 이 점이 처음으로 n-1, m-1칸에 도착했으면 거리를 출력하고 return 한다.
코드
'Algorithm' 카테고리의 다른 글
| 백준 - 1285번(동전 뒤집기) / C++ (0) | 2021.03.26 |
|---|---|
| 프로그래머스 - 카드 짝 맞추기 / C++ (2) | 2021.03.24 |
| 백준 - 14939번(불 끄기) / C++ (0) | 2021.03.12 |
| 백준 - 17831번(머기업 승범이네) / C++ (0) | 2021.03.10 |
| 프로그래머스 - 매출 하락 최소화 / C++ (2) | 2021.03.08 |