쌓고 쌓다
[프로그래머스] 게임 맵 최단거리 C++ 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/1844
풀이 방법
간단히 BFS를 통해 풀 수 있는 문제이다.
미로의 크기가 최대 100x100이지만
방문 여부를 MAP을 사용하여 풀려고 했으나 사용했더니 효율성 부분에서 시간초과로 다 틀려버린다.
방문 여부를 그냥 2차원 배열을 통해 확인하도록 하자.
전체 코드
#include<vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> maps)
{
int answer = -1;
queue<pair<int,pair<int,int>>> q; // (cnt,y,x)
bool visit[100][100];
fill(&visit[0][0], &visit[99][100], false);
if(maps[0][0]==1) {
q.push(make_pair(1,make_pair(0,0)));
visit[0][0]=true;
}
while(!q.empty()){
int x, y, cnt;
cnt = q.front().first;
x = q.front().second.second;
y = q.front().second.first;
q.pop();
if(x==maps[0].size()-1 && y==maps.size()-1) {
answer=cnt;
break;
}
if(y-1>=0 && maps[y-1][x]==1 && visit[y-1][x]==false) {
q.push(make_pair(cnt+1,make_pair(y-1,x)));
visit[y-1][x]=true;
}
if(y+1<=maps.size()-1&&maps[y+1][x]==1 && visit[y+1][x]==false) {
q.push(make_pair(cnt+1,make_pair(y+1,x)));
visit[y+1][x]=true;
}
if(x-1>=0&&maps[y][x-1]==1 && visit[y][x-1]==false) {
q.push(make_pair(cnt+1,make_pair(y,x-1)));
visit[y][x-1]=true;
}
if(x+1<=maps[0].size()&&maps[y][x+1]==1 && visit[y][x+1]==false) {
q.push(make_pair(cnt+1,make_pair(y,x+1)));
visit[y][x+1]=true;
}
}
return answer;
}
방문 여부를 MAP으로 사용한 코드 ( map 사용시 효율성 부분에서 시간초과남 )
#include<vector>
#include <queue>
#include <map>
using namespace std;
int solution(vector<vector<int>> maps)
{
int answer = -1;
queue<pair<int,pair<int,int>>> q; // (cnt,y,x)
map<pair<int,int>, bool> m; // 방문 여부
if(maps[0][0]==1) {
q.push(make_pair(1,make_pair(0,0)));
m.insert({make_pair(0,0), true});
}
while(!q.empty()){
int x, y, cnt;
cnt = q.front().first;
x = q.front().second.second;
y = q.front().second.first;
q.pop();
if(x==maps[0].size()-1 && y==maps.size()-1) {
answer=cnt;
break;
}
if(y-1>=0 && maps[y-1][x]==1 && m.find(make_pair(y-1,x))==m.end()) {
q.push(make_pair(cnt+1,make_pair(y-1,x)));
m.insert({make_pair(y-1,x), true});
}
if(y+1<=maps.size()-1&&maps[y+1][x]==1 && m.find(make_pair(y+1,x))==m.end()) {
q.push(make_pair(cnt+1,make_pair(y+1,x)));
m.insert({make_pair(y+1,x), true});
}
if(x-1>=0&&maps[y][x-1]==1 && m.find(make_pair(y,x-1))==m.end()) {
q.push(make_pair(cnt+1,make_pair(y,x-1)));
m.insert({make_pair(y,x-1), true});
}
if(x+1<=maps[0].size()&&maps[y][x+1]==1 && m.find(make_pair(y,x+1))==m.end()) {
q.push(make_pair(cnt+1,make_pair(y,x+1)));
m.insert({make_pair(y,x+1), true});
}
}
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 뒤에 있는 큰 수 찾기 C++ 풀이 및 해설 (0) | 2023.06.29 |
---|---|
[프로그래머스] 모음사전 C++ 풀이 및 해설 (0) | 2023.06.26 |
[프로그래머스] [3차] 파일명 정렬 C++ 풀이 및 해설 (0) | 2023.05.03 |
[프로그래머스] 방문 길이 C++ 풀이 및 해설 (0) | 2023.03.24 |
[프로그래머스] 땅따먹기 C++ 풀이 및 해설 (0) | 2023.03.20 |
Comments