[프로그래머스] 보행자 천국 (C++)

문제 링크: programmers.co.kr/learn/courses/30/lessons/1832

코딩테스트 연습 - 보행자 천국

1. 주의할 점

- Check[][][] 배열이 갱신될 때마다 MOD로 나눈 나머지를 저장한다

- (Y,X)에 Dir의 방향에서부터 온 적이 여러번 있다면, 최종 경우에만 BFS를 수행하도록 한다 (안하면 메모리 초과 가능성↑)

 

2. 구현

- 2 방향으로만 이동가능하므로 항상 특정 지점까지의 거리는 최단거리로 구해진다 → Info 구조체를 큐에 삽입하여 BFS를 수행한다

- Check[Y][X][Dir] 배열을 통해 (Y,X)에 Dir의 방향에서 몇번 왔는지 저장하기 위해 초기화하고 시작한다

- (0,0)은 항상 0이므로 큐에는 1개만 삽입하고 시작한다. 동시에 Check[0][0][0], Check[0][0][1]을 전부 1로 초기화한다

- BFS를 수행하며 CV와 Check[][][]를 비교하여 가장 마지막으로 해당 지점에 방문하면서 추가된 원소가 아니라면 Continue를 통해 불필요한 연산을 제거한다

- 현재 위치가 오른쪽 아래라면 Answer에 현재값만큼 더하고 MOD로 나눈 이후, Continue를 수행한다

- 현재 위치가 1이라면 Continue를 통해 이동하지 못하도록 하며, 2라면 진행하려는 방향이 기존 방향과 같을 때에만 전진한다

- 큐에 추가될 경우, 마지막으로 방문한 이동하도록 Check[][][]값을 갱신한다

#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct info{
    int y,x,dir,val;
};
info tmp;
int MOD = 20170805;
int dx[2]={0,1};
int dy[2]={1,0};
int check[500][500][2];

int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<2;k++)
                check[i][j][k]=0;
    queue<info> q;
    for(int i=0;i<2;i++){
        check[0][0][i]=1;
    }
    q.push({0,0,0,1});
    
    while(!q.empty()){
        int cx = q.front().x;
        int cy = q.front().y;
        int cd = q.front().dir;
        int cv = q.front().val;
        q.pop();
        if(check[cy][cx][cd]!=cv) continue;
        if(cy==m-1 && cx==n-1){
            answer = (answer+cv)%MOD;
            continue;
        }
        int ca = city_map[cy][cx];
        if(ca==1) continue;
        for(int i=0;i<2;i++){
            if(ca==2 && cd!=i) continue;
            int nx = cx+dx[i];
            int ny = cy+dy[i];
            if(nx>=0 && ny>=0 && nx<n && ny<m){
                check[ny][nx][i]=(check[ny][nx][i]+cv)%MOD;
                q.push({ny,nx,i,check[ny][nx][i]});
            }
        }
    }
    return answer;
}