SWEA - 1249 보급로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

복구에 가장 적은 시간이 드는 경로를 찾아 최소 시간을 구하는 문제였다.

 

문제 풀이

처음에 당연히 int로 입력될 것이라 생각하고 했더니 입력에서 오류가 나서 당황했다. 문제를 자세히 보니.. string으로 입력을 받아야 해서 굳이 이렇게..? 라는 생각을 하긴 했지만 바꿔서 입력받았다.

 

우선순위 큐를 이용해 걸리는 시간이 짧은 곳부터 방문하도록 했다. 처음에는 메모리 limit을 넘었다는 오류가 계속 났는데, bfs를 똑같은 방법으로 다시 짜니까 해결됐다. 뭐가 문제였는진 모르겠지만 실수를 한 부분이 있었던 것 같다.

 

뭔지 모르겠는 오류가 날 때는 다시 짜는 게 더 빠르다는 것을 항상 명심할 것!

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

using namespace std;       

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

void printMap(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            printf("%d",map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

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

void bfs(int x, int y){
	priority_queue<pair<int,pair<int,int>>> pq;
    
    pq.push({0,{x,y}});
    
    while(!pq.empty()){
        int nowTime = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        visit[x][y] = 1;
        pq.pop();
        
        if(x == N-1 && y == N-1){
            minTime = nowTime;
            break;
        }                
        
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(isInside(nx,ny) && visit[nx][ny] == 0){
				int nextTime = nowTime + map[nx][ny];
                pq.push({-nextTime, {nx,ny}});
            }                        
        }
    }
    
}

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);
        string s;
        minTime = 98765432;
        fill(&map[0][0], &map[100][100], 0);
        fill(&visit[0][0], &visit[100][100], 0);
        for(int i=0;i<N;i++){
            cin>>s;
            for(int j=0;j<N;j++){         		
                map[i][j] = s[j]-'0';
            }
        }
        
        bfs(0,0);

		//printMap();        
        printf("#%d %d\n",test_case, minTime);


	}
	return 0;
}