SWEA - 4193 수영대회 결승전

문제

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV

SW Expert Academy

맵에 규칙적으로 생성되고 사라지는 소용돌이가 있다. 이를 감안해서 출발지부터 목적지까지 가장 빠르게 도달하는 최단 경로를 구하는 문제였다.

 

문제 풀이

우선순위 큐를 이용해 bfs로 풀었다. 이때 다음 위치가 소용돌이라면 기다려야 하는 시간을 계산해서 더해서 queue에 넣어줬다. 가장 먼저 목적지에 도달한 경로가 최단 경로이다.

 

처음에 info 구조체에 visit vector를 넣어서 시간 초과가 났었다. 왜 그렇게 구현했었는지 잘 모르겠지만 visit는 항상 하나만 있으면 된다! (이전까지는 하나로만 하다가 대체 왜 이 문제에서는 visit를 queue에 넣을 생각을 했지?)

 

어쨌든 풀었다 우하하

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include <queue>

#define INT_MAX 98765432

using namespace std;

typedef struct info{
    int time;
    int x;
    int y;
}info;

struct compare{
	bool operator()(const info &info1, const info &info2){
     	return info1.time > info2.time;   
    }
};

int N;
int minTime;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

info makeInfo(int x, int y, int time){
    info i;
    i.x = x;
    i.y = y;
    i.time = time;
    return i;
}

bool isInsideMap(int x, int y){
    if(x >= 0 && y >= 0 && x < N && y < N) return true;
    else return false;
}

void bfs(int x, int y, vector<vector<int>> map, int endX, int endY){
 	priority_queue<info, vector<info>, compare> pq;
    vector<vector<int>> visit(N, vector<int>(N,0));
    visit[x][y] = 1;
	pq.push(makeInfo(x,y,0));
    
    while(!pq.empty()){
        info nowInfo = pq.top();
        int x = nowInfo.x;
        int y = nowInfo.y;
        int time = nowInfo.time;
        visit[x][y] = 1;
        pq.pop();
        
        if(x == endX && y == endY){
            minTime = time;
            return;
        }
        
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(isInsideMap(nx,ny) && visit[nx][ny] == 0 && map[nx][ny] != 1){
                if(map[nx][ny] == 0) pq.push(makeInfo(nx,ny,time+1));
                else if(map[nx][ny] == 2){
                    //소용돌이 언제 열리는지 시간 계산
                    pq.push(makeInfo(nx,ny,time+ 2 - time%3 + 1));                    
                }
            }
        }
    }
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin>>T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        scanf("%d",&N);
        vector<vector<int>> map(N,vector<int>(N));
        
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                scanf("%d",&map[i][j]);
            }
        }
        int startX, startY, endX, endY;
        scanf("%d %d",&startX, &startY);
        scanf("%d %d",&endX, &endY);

        minTime = INT_MAX;
        bfs(startX, startY, map, endX, endY);
        if(minTime == INT_MAX) minTime = -1;
        
        printf("#%d %d\n",test_case, minTime);
	}
	return 0;
}