n<=15, 테케 15개 2초이므로 시간에 크게 구애받지 않음.
최단 시간, 경로이므로 bfs, dfs를 생각할 수 있음.
한 지점에서 특정 한지점이므로 bfs를 선택.
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#define MAX 987654321
using namespace std;
struct Pos {
int x;
int y;
Pos(int X,int Y) : x(X),y(Y){};
};
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n,answer;
Pos start(0,0), arrive(0,0);
vector <vector<int>> arr;
vector <vector<int>> visited;
queue <pair<int, Pos>> bfs;
void getAnswer();
bool canGo(vector <vector<int>>, int, int,int);
int main(int argc, char** argv)
{
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> n;
arr.resize(15, vector <int>(15));
visited.resize(15, vector <int>(15,0));
bfs = queue <pair<int, Pos>>();
answer = MAX;
//배열 입력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
visited[i][j] = 0;
}
}
int x, y;
cin >> x >> y;
start.x = x;
start.y = y;
cin >> x >> y;
arrive.x = x;
arrive.y = y;
bfs.push(make_pair(0, start));
// bfs 돌기
getAnswer();
if(answer==MAX)cout << "#" << test_case << " " << -1 << endl;
else {
cout << "#" << test_case << " " << answer << endl;
}
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
void getAnswer() {
visited[start.x][start.y]=1;
while (!bfs.empty()) {
pair <int,Pos> p = bfs.front();
bfs.pop();
int currTime = p.first;
Pos currPos = p.second;
if (currPos.x == arrive.x && currPos.y == arrive.y) {
answer = currTime;
break;
}
//1. 기다리기
if(visited[currPos.x][currPos.y]<3){
bfs.push(make_pair(currTime + 1,currPos));
visited[currPos.x][currPos.y]++;
}
//2. 움직이기
for (int i = 0; i < 4; i++)
{
int nextX = currPos.x + dx[i];
int nextY = currPos.y + dy[i];
if (canGo(arr, nextX, nextY,currTime)) {
visited[nextX][nextY] = 1;
bfs.push(make_pair(currTime + 1, Pos(nextX, nextY)));
}
}
}
}
bool canGo(vector <vector<int>> v, int x, int y,int currTime) {
//배열 범위 안일때
if (x >= 0 && x < n && y >= 0 && y < n) {
//장애물이 아니고 아직 안간 곳일 때
if (arr[x][y]!=1&&visited[x][y]==0) {
if (arr[x][y] != 2) return true;
else {
//소용돌이인데 시간 상 건너갈 수 있을 때
if (currTime % 3 == 2) return true;
}
}
}
return false;
}
다른 사람들의 실행 시간을 보니 10ms 대 였다...
당황,,😱 완벽한 풀이가 아니라고 생각해서 다시 풀어보았다.
1. canGo에 if문을 switch문으로 바꿨다.
=>실행시간이 50ms에서 39ms로 단축