[BOJ] - 9019. DSLR [BFS] - c++

ha·2022년 2월 9일
0

BOJ

목록 보기
28/28

https://www.acmicpc.net/problem/9019

C++ BFS풀이

BFS템플릿 적용 (queue 사용)
1.for 문 내부 4방향 이동 -> L,R,S,D로 직접 대체
2.queue내부 pair형태<좌표, 현재까지 이동경로(DSLR)>
3.종결 조건 : 좌표 ==End

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int tc;
int start;int End;
bool vis[10000];

int main() {
    cin>>tc;


    while(tc--)
    {
        memset(vis,false,sizeof(vis));
        cin>>start>>End;
        queue<pair<int,string>> q;
        q.push(make_pair(start,""));
        vis[start]=true;
        while(!q.empty())
        {
        int cur = q.front().first;
        string s=q.front().second;
        q.pop();

        if(cur==End) {cout<<s<<'\n';break;}

        int nx = cur*2;
        if(nx>9999) nx %= 10000;
        if(vis[nx]==false)
        {
            q.push(make_pair(nx,s+"D"));
            vis[nx]=true;
        }

        nx = cur-1;
        if(nx<0) nx = 9999;
        if(vis[nx]==false)
        {
            q.push(make_pair(nx,s+"S"));
            vis[nx]=true;
        }

        nx = (cur%1000)*10 + cur/1000;
        if(vis[nx]==false)
        {
            q.push(make_pair(nx,s+"L"));
            vis[nx]=true;
        }

        nx = (cur%10)*1000 + (cur/10);
        if(vis[nx]==false)
        {
            q.push(make_pair(nx,s+"R"));
            vis[nx]=true;
        }
        }    
    }
    return 0;
} 

0개의 댓글