[SWEA] 1249번. 보급로 (C++)

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=CCPP&select-1=4&pageSize=10&pageIndex=1

SW Expert Academy

 

풀이

BFS로 풀면 된다

 

그나마 조금 다른점은(?)

if (nsum>=distance[ny][nx]) continue;

이 부분일것이다.

더 작은 합을 선택하기 위해 이렇게 진행한다.

 

#include<iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>>dir={{-1,0},{1,0},{0,-1},{0,1}};

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

	for(int test_case = 1; test_case <= T; ++test_case)
	{
        //INPUT////////////////////////////////////////////
        int N; cin>>N;
        vector<vector<int>>m(N,vector<int>(N,0));
        vector<vector<int>>distance(N,vector<int>(N,200000000));
        for(int i=0;i<N;i++)
        {
            string s; cin>>s;
            for(int k=0;k<s.size();k++){   m[i][k]=s[k]-'0';   }
        }
        
		//FIRST//////////////////////////////////////////////
		queue<vector<int>> q;
        q.push( { 0,0,0 } );
        distance[0][0]=0;
        
        //START//////////////////////////////////////////////
        while(!q.empty())
        {
            int x=q.front()[0];
            int y=q.front()[1];
            int sum=q.front()[2];
            
            q.pop();
            
            for(int i=0;i<4;i++)
            {
                int nx=x+dir[i][0];
                int ny=y+dir[i][1];
                
                if(nx<0||ny<0||nx>=N||ny>=N) continue; //out of boundary
                
                int nsum=sum+m[ny][nx];
                if (nsum>=distance[ny][nx]) continue; //select smaller one
                distance[ny][nx]=nsum;
                q.push({nx,ny,nsum});
            }
        }
		cout<<"#"<<test_case<<" "<<distance[N-1][N-1]<<"\n";
	}
	return 0;
}

 

프로그래머스에서 비슷한 문제를 풀었던것 같다