[Softeer/소프티어][level3] 차세대 지능형 교통시스템 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=580&sw_prbl_sbms_sn=17217

Softeer

 

 

[난이도] level3
[유형] BFS

[풀이]
visit[100][100][4][4] 짜리 4차원 배열로 방문 체크를 해줘야하는 BFS 문제입니다.
visit[y][x][t][d] t : 현재시간, d : 현재방향
위와 같이 방향 뿐만 아니라 현재 시간에 따라서도 다른 상태가 될 수 있는 것을 주의해야 합니다.
T1%4 == T2%4 라면  T1과 T2는 같은 시간으로 쳐도 되므로 4의 공간만 필요합니다.

33번 라인의 코드
if(signals[seq[y][x][t%4]][0]!=d) continue; 는
t시간에 d의 방향으로 y,x에 방문한 상태일 때, y,x의 현재 신호가 유효한지를 체크해서 유효지 않으면 무시하는 로직입니다.

예를 들어, 차량의 방향이 위를 보고 있다면, 위 방향을 가리키고 있는 2,6,10 신호만 유효한 신호입니다.
signals vector에 신호 방향을 저장할 때, 0번 index에는 항상 좌,우회전이 아닌 직진 방향을 저장함으로써 0번 index만을 체크해서 유효성을 확인하였습니다.

 

#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int dy[4] = {0,-1,0,1}, dx[4] = {1,0,-1,0};
struct P{int y,x,d;};
vector<int> signals[13] = { {},
    {0,1,3},{1,0,2},{2,1,3},{3,0,2},
    {0,1},{1,2},{2,3},{3,0},
    {0,3},{1,0},{2,1},{3,2}
};
int N,T,seq[100][100][4];
bool visit[100][100][4][4];
set<pair<int,int>> ans;
int main(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<4;k++)
                scanf("%d",&seq[i][j][k]);
    queue<P> q;
    q.push({0,0,1});
    visit[0][0][0][1]=1;
    ans.insert({0,0});
    int t=0;
    while(!q.empty()){
        int sz =q.size();
        if(t==T) break;
        while(sz--){
            auto [y,x,d] = q.front(); q.pop();
            if(signals[seq[y][x][t%4]][0]!=d) continue;

            for(auto k : signals[seq[y][x][t%4]]){
                int ny = y+dy[k], nx = x+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=N||visit[ny][nx][t%4][k]) continue;
                visit[ny][nx][t%4][k]=1;
                q.push({ny,nx,k});
                ans.insert({ny,nx});
            }
        }
        t++;
    }
    printf("%d",ans.size());
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/차세대_지능형_교통시스템.cpp