https://programmers.co.kr/learn/courses/30/lessons/1844
코딩테스트 연습 - 게임 맵 최단거리
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1
programmers.co.kr
1) 풀이
요즘 BFS, DFS 문제를 백준에서 집중적으로 다시 풀어보다가,
프로그래머스에서는 한 번도 이 알고리즘문제를 풀어본 적이 없어서 풀어보았다!
사실 기존의 BFS 풀이랑 별반 다를 건 없는데,
백준과 푸는 방식? 제출 방식? 뭐라고 해야 하나.
아무튼.. 그게 달라서 적응이 좀 필요할 것 같다 😂
푸는 방법자체는 아래의 글과 같으니 참고 바람!
2021.06.01 - [알고리즘 | 자료구조/백준] - [백준/c++] 2178 - 미로 탐색
[백준/c++] 2178 - 미로 탐색
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. ww..
sebada.tistory.com
2) 최종 소스코드
#include<vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int arr[102][102]; //도착하는 칸 거리
int tx[4]={0,1,0,-1}; //상하좌우 X 좌표
int ty[4]={1,0,-1,0}; //상하좌우 Y좌표
int solution(vector<vector<int> > maps)
{
int answer = 0;
memset(arr,-1,sizeof(arr)); //-1로 거리 배열 초기화
queue<pair<int,int>>q; //탐색 좌표 담을 QUEUE
q.push({0,0});
arr[0][0]=1; // 첫칸을 포함하므로 첫칸을 1로 초기화
while(!q.empty()){
pair<int,int>cur=q.front();
q.pop();
for(int k=0;k<4;k++){
int dx=cur.first+tx[k];
int dy=cur.second+ty[k];
if(dx<0||dx>=maps.size()||dy<0||dy>=maps[0].size()) continue;
if(arr[dx][dy]>=0||maps[dx][dy]==0) continue;
q.push({dx,dy});
arr[dx][dy]=arr[cur.first][cur.second]+1;
}
}
answer=arr[maps.size()-1][maps[0].size()-1]; //제일 끝 칸이 곧 몇개 칸을 지나서 왔는지
return answer;
}
3) 참고자료
728x90
'Problem Solving > 프로그래머스' 카테고리의 다른 글
[프로그래머스/c++] 폰켓몬 (0) | 2021.06.16 |
---|---|
[프로그래머스/c++] 완주하지 못한 선수 (0) | 2021.06.13 |
[프로그래머스/c++] 체육복 (0) | 2021.06.03 |
[프로그래머스/JavaScript] 3진법 뒤집기 (0) | 2021.05.20 |
[프로그래머스/JavaScript] 두 정수 사이의 합 (0) | 2021.05.10 |