[SWEA] 수영대회 결승전

문제 링크

내 문제 풀이 빌드업

1. n<=15, 테케 15개 2초이므로 시간에 크게 구애받지 않음.

2. 최단 시간, 경로이므로 bfs, dfs를 생각할 수 있음.

3. 한 지점에서 특정 한지점이므로 bfs를 선택.

   시행착오

• bfs는 많이 풀어봐서 큰 틀 코딩까지는 얼마 안걸렸지만 테케 하나에서 시간초과가 계속 났다.
• bfs에서 시간초과라 하면 방문처리밖에 없다고 생각해서 다른 bfs와 다른 점인 소용돌이를 기다리는 경우에 대해 생각해봄.
• 모든 시점에서 기다리는 경우를 큐에 넣어줘서 큐가 비지 않았음.
• 방문 처리에 횟수 제한을 둬서 3번 이상은 큐에 넣어주지 않음

  정답 풀이

#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로 단축