[BOJ 2206] 벽 부수고 이동하기

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

음 ... 딱봐도 bfs 문제이다. 문제접근을 

1) bfs 로 이동 

2) 벽을 깨고 이동하는 경우와 아닌 경우를 구분해서 구현

이렇게 접근을 하는데 방문했던 지점을 어떻게 처리를 해야할지를 몰라서 해맸다 ... 

방법은 3차원 visit배열을 구현하여 벽을 깬적이 없으면 [y][x][1]부분에, 깬적이 있으면 [y][x][2]부분에서 visit처리를 해주었다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
 
 
using namespace std;
 
int n,m,arr[1111][1111], ans;
bool visit[1111][111][3];
 
queue<pair<int,pair<int,pair<int,int>>>> q;
 
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
 
bool chk(int a,int b){
    return a<=n && a>=1 && b<=m && b>=1;
}
 
int main(){
    memset(visit,false,sizeof(visit));
    ans = 100000000;
    scanf("%d%d" , &n,&m);
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%1d" , &arr[i][j]);
        }
    }
    q.push({1,{1,{0,1}}});
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second.first;
        int c = q.front().second.second.first;
        int cnt = q.front().second.second.second;
        q.pop();
        if(x == m && y == n){
            if(ans>cnt){
                ans = cnt;
            }
            continue;
        }
        if(c == 0){
            for(int i=0;i<4;i++){
                int xx = x+dx[i];
                int yy = y+dy[i];
                if(chk(yy,xx) && visit[yy][xx][1] == false){
                    if(arr[yy][xx] == 1){
                        q.push({yy,{xx,{1,cnt+1}}});
                        visit[yy][xx][2] = true;
                    }else{
                        q.push({yy,{xx,{0,cnt+1}}});
                        visit[yy][xx][1] = true;
                    }
                }
            }
            
        }else if(c == 1){
            for(int i=0;i<4;i++){
                int xx = x+dx[i];
                int yy = y+dy[i];
                if(chk(yy,xx) && visit[yy][xx][2] ==false){
                    if(arr[yy][xx] == 0){
                        q.push({yy,{xx,{1,cnt+1}}});
                        visit[yy][xx][2] = true;
                    }
                }
            }
        }
        
    }
    if(ans == 100000000){
        printf("-1\n");
        return 0;
    }
    printf("%d\n" ,ans);
    return 0;
}

※느낀점 - 아 struct 사용하자 ㅋㅋㅋㅋㅋㅋㅋpair노답 ㅋㅋㅋㅋㅋㅋ