백준, BOJ, 5573번, 산책 : C++ [CPP]

이거 왜 이렇게 풀었지?라고 생각했는데

진짜 이렇게 풀려서 당황했다.

 

나는.. 진짜 플레를 풀 줄 몰랐다.

근데 그냥 이렇게 풀면되지 않을까? 했는데 풀렸다.

 

난이도 내려야할 듯하다.

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

//1: 오른쪽   0: 아래쪽
const int MAX = 1003;

int H,W,N; //세로, 가로, N번째 일 

int road[MAX][MAX];
int dp[MAX][MAX]; //N일까지 해당 위치를 지나간 횟수 

int main(){
    cin >> H >> W >> N;
    
    for(int i=1; i<=H; i++){
         for(int j=1; j<=W; j++){
             cin >> road[i][j];
         }   
    }

    //어느 위치에서 종료하느냐?
    //N-1일차까지 경로가 수정된 N일차를 탐색하면 된다.
    //또한 경로가 지나갈 때마다 수정되니 해당 경로를 몇번 방문하는지를 생각한다.
    dp[1][1] = N-1;
    for(int i = 1; i<=H; i++){
        for(int j = 1; j<=W; j++){
            
            dp[i+1][j] += dp[i][j]/2;//해당 위치의 아래쪽으로 가는 경우의 수
            dp[i][j+1] += dp[i][j]/2;//해당 위치의 오른쪽으로 가는 경우의 수
            
            
            if(dp[i][j]&1){
                //홀수면 road초기의 방향에 따라 오른쪽이 한 번 더갈지
                //아래쪽으로 한 번 더 갈지 다름.
                //만약 처음에 해당쪽으로 한번 더
                if(road[i][j] == 1) dp[i][j+1]++;
                else dp[i+1][j]++;
            }
            //방문 수만큼 바뀜 -> 2번바뀌면 바뀌지 않은 것이랑 같음
            int toggle = (dp[i][j]%2);
            
            //toggle이 1이라면 road[i][j]의 상태가 바뀌어야함.
            //toggle이 0이라면 road[i][j]는 그대로
            //XOR은 다르면 1 같으면 0이나옴 
            //-> toggle이 1이고 road[i][j]가 1이면 0이되어야함.
            //-> toggle이 1이고 road[i][j]가 0이면 1이되어야함.
            //-> toggle이 0이고 road[i][j]가 0이면 0이되어야함.
            //-> toggle이 0이고 road[i][j]가 1이면 1이 되어야함
            if(toggle)road[i][j] ^= toggle;

        }
    }
    
    //N-1날 이후 경로 만든 뒤 탐색
    queue<pair<int,int>> q;
    q.push({1,1});
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        int nr, nc;
        
        if(road[cur.first][cur.second] == 1){
            nr = cur.first;
            nc = cur.second+1;
        }else{
            nr = cur.first+1;
            nc = cur.second;
        }
        
        if(nr == H+1 || nc == W+1){
            cout << nr << ' ' << nc << '\n';
            break;
        }else{
            q.push({nr,nc});
        }
    }
    

    
    return 0;
    
}